Competitive Programming►Problems

TIOJ 1396 - 線段覆蓋

Link: http://tioj.ck.tp.edu.tw/problems/1396

code隨便亂寫，總覺得這題測資很弱，誤會題意時居然就亂寫AC了

分別A,B需要幾步驟再比較即可
這題比較需要注意的是當X==Y時，要特判如果有覆蓋到這點代表只需1步，沒有則無法獲勝。

AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <algorithm>
#define INF 1000100
using namespace std;
pair<int,int> ax[100010],bx[100010];
int l,r;
int solve(int n,pair<int,int> *x)
{
    if(l==r)
    {
        for(int i=0;i<n;i++)
            if(x[i].first<=l&&x[i].second>=r)
                return 1;
        return INF;
    }
    sort(x,x+n);
    int cur=l,nxt=l;
    int ans=0;
    for(int i=0;i<=n;i++)
    {
        if(i==n || x[i].first>cur)
        {
            ans++;
            cur=nxt;
            if(cur>=r)
                return ans;
            if(i==n || x[i].first>cur)
                return INF;
        }
        nxt=max(nxt,x[i].second);
    }
    throw;
} 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
            cin>>ax[i].first>>ax[i].second;
        for(int i=0;i<m;i++)
            cin>>bx[i].first>>bx[i].second;
        cin>>l>>r;
        int a=solve(n,ax);
        int b=solve(m,bx);
//     cout<<a<<' '<<b<<endl;
     if(a==INF && b==INF)
            cout<<"TIE"<<endl;
        else if(a<=b)
            cout<<"A WIN"<<endl;
        else
            cout<<"B WIN"<<endl;
    }
}