oj.uz

Submission #1036796

# Submission time Handle Problem Language Result Execution time Memory
1036796 2024-07-27T17:17:25 Z anango Alternating Current (BOI18_alternating) C++17
55 / 100
 3000 ms 7076 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int INF = 1LL<<30;

int n,m; 
vector<pair<int,int>> segments;
vector<int> indices,invindices;


bool inside(int a, int b, int c) {
    //is it a,b,c in this order?
    bool ans = (a<=b && b<=c) || (a<=b && b>c && c<a) || (a>b && b<=c && c<a);
    ////cout << a <<" " << b <<" " << c <<" " << ans << endl;
    return ans;
}

bool between(pair<int,int> s1, pair<int,int> s2, int ind1, int ind2) {
    //is s2 fully between s1's endpoints
    int a=s1.first; int b = s1.second; int c = s2.first; int d = s2.second;
    bool ans = inside(a,c,d) && inside(c,d,b) && inside(a,c,b) && inside(a,d,b);
    ////cout << a <<" " << b <<" " << c <<" " <<d << " " << ans << endl;
    if (a==c && b==d) {
        return ind1<ind2;
    }
    return ans;
}

bool works(vector<int> ans) {
    
    //1 implies 0-covered, 2 implies 1-covered
    set<int> remset0;
    set<int> remset1;
    for (int i=0; i<n; i++) {
        remset0.insert(i); remset1.insert(i);
    }
    for (int i1=0; i1<m; i1++) {
        int l = segments[i1].first;
        int r = segments[i1].second;
        for (int i=l; i!=r; ) {
            //cout << "erasing " << i <<" " << l <<" " <<r <<" " << ans[i1] << endl;
            if (ans[i1]==0 && remset0.count(i)) {
                remset0.erase(i);
            }
            if (ans[i1]==1 && remset1.count(i)) {
                remset1.erase(i);
            }
            i++; i%=n;
        }
        if (ans[i1]==0 && remset0.count(r)) {
            remset0.erase(r);
        }
        if (ans[i1]==1 && remset1.count(r)) {
            remset1.erase(r);
        }
    }
    return (remset0.size()==0) && (remset1.size()==0);
}

void print_ans(vector<int> answer){
    for (int i=0; i<m; i++) {
        //cout << invindices[i] <<" ";
    }
    //cout << endl;
    for (int i=0; i<m; i++) {
        cout << answer[invindices[i]];
    }
    cout << endl;
}

signed main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        //freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        //freopen("output.txt", "w", stdout);
    #endif
    #ifdef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif //fast IO
    cin >> n >> m;
    vector<int> answer(m,-1);
    indices=invindices=vector<int>(m); iota(indices.begin(), indices.end(), (int)0);
    for (int i=0; i<m; i++) {
        int s,t; cin >> s >> t; s--; t--;
        segments.push_back({s,t}); //subtask 4: t>s
    }
    stable_sort(indices.begin(), indices.end(), [&](const int i1, const int i2) {
        return segments[i1]<segments[i2];
    });
    for (int i=0; i<m; i++) {
        invindices[indices[i]] = i;
    }
    stable_sort(segments.begin(), segments.end());
    vector<int> goods;
    vector<int> covered_by(m,-1);
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            if (j==i) continue;
            //if i is covered by j
            if (between(segments[j],segments[i],j,i)) {
                covered_by[i] = j;
            }
        }
        if (covered_by[i]==-1) {
            goods.push_back(i);
        }
    } 
    for (int i=0; i<m; i++) {
        //cout << i << " " << covered_by[i] << endl;
    }
    int k = goods.size();
    if (goods.size()%2==0) {
        for (int i=0; i<k; i++) {
            //cout << "setting " << goods[i] <<" " << i%2 << endl;
            answer[goods[i]] = i%2;
        }
        for (int i=0; i<m; i++) {
            if (covered_by[i]!=-1) {
                //cout << "setting2 " << i <<" " << covered_by[i] <<" " <<answer[covered_by[i]] << endl;
                answer[i] = 1-answer[covered_by[i]];
            }
        }
        for (int i=0; i<m; i++) {
            if (answer[i]!=0 && answer[i]!=1) {
                answer[i] = 0;
            }
        }
    }
    else {
        for (int tau=0; tau<k; tau++) {
            for (int i=0; i<tau; i++) {
                answer[goods[i]] = i%2;
            }
            for (int i=tau; i<k; i++) {
                answer[goods[i]] = (i+1)%2;
            }
            for (int i=0; i<m; i++) {
                if (covered_by[i]!=-1) {
                    answer[i] = 1-answer[covered_by[i]];
                }
            }
            for (int i=0; i<m; i++) {
                if (answer[i]!=0 && answer[i]!=1) {
                    answer[i] = 0;
                }
            }
            if (works(answer)) {
                break;
            }
        }
    }
    //cout << "trying answer " << endl;
    if (works(answer)) {
        print_ans(answer);
    }
    else {
        cout << "impossible" << endl;       
    }

    
    
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 1 ms 604 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 1 ms 348 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
66 Correct 1 ms 348 KB Output is correct
67 Correct 1 ms 348 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 1 ms 604 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 1 ms 348 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
66 Correct 1 ms 348 KB Output is correct
67 Correct 1 ms 348 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 12 ms 348 KB Output is correct
71 Correct 156 ms 348 KB Output is correct
72 Correct 4 ms 348 KB Output is correct
73 Correct 1 ms 348 KB Output is correct
74 Correct 1 ms 348 KB Output is correct
75 Correct 0 ms 348 KB Output is correct
76 Correct 4 ms 348 KB Output is correct
77 Correct 4 ms 600 KB Output is correct
78 Correct 10 ms 348 KB Output is correct
79 Correct 1 ms 348 KB Output is correct
80 Correct 4 ms 348 KB Output is correct
81 Correct 1 ms 348 KB Output is correct
82 Correct 1 ms 348 KB Output is correct
83 Correct 3 ms 348 KB Output is correct
84 Correct 5 ms 348 KB Output is correct
85 Correct 1 ms 348 KB Output is correct
86 Correct 1 ms 348 KB Output is correct
87 Correct 3 ms 348 KB Output is correct
88 Correct 1 ms 348 KB Output is correct
89 Correct 727 ms 536 KB Output is correct
90 Correct 8 ms 348 KB Output is correct
91 Correct 1 ms 348 KB Output is correct
92 Correct 4 ms 348 KB Output is correct
93 Correct 1 ms 348 KB Output is correct
94 Correct 0 ms 348 KB Output is correct
95 Correct 1 ms 436 KB Output is correct
96 Correct 5 ms 348 KB Output is correct
97 Correct 5 ms 348 KB Output is correct
98 Correct 5 ms 348 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 7076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 1 ms 604 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 1 ms 348 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
66 Correct 1 ms 348 KB Output is correct
67 Correct 1 ms 348 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 12 ms 348 KB Output is correct
71 Correct 156 ms 348 KB Output is correct
72 Correct 4 ms 348 KB Output is correct
73 Correct 1 ms 348 KB Output is correct
74 Correct 1 ms 348 KB Output is correct
75 Correct 0 ms 348 KB Output is correct
76 Correct 4 ms 348 KB Output is correct
77 Correct 4 ms 600 KB Output is correct
78 Correct 10 ms 348 KB Output is correct
79 Correct 1 ms 348 KB Output is correct
80 Correct 4 ms 348 KB Output is correct
81 Correct 1 ms 348 KB Output is correct
82 Correct 1 ms 348 KB Output is correct
83 Correct 3 ms 348 KB Output is correct
84 Correct 5 ms 348 KB Output is correct
85 Correct 1 ms 348 KB Output is correct
86 Correct 1 ms 348 KB Output is correct
87 Correct 3 ms 348 KB Output is correct
88 Correct 1 ms 348 KB Output is correct
89 Correct 727 ms 536 KB Output is correct
90 Correct 8 ms 348 KB Output is correct
91 Correct 1 ms 348 KB Output is correct
92 Correct 4 ms 348 KB Output is correct
93 Correct 1 ms 348 KB Output is correct
94 Correct 0 ms 348 KB Output is correct
95 Correct 1 ms 436 KB Output is correct
96 Correct 5 ms 348 KB Output is correct
97 Correct 5 ms 348 KB Output is correct
98 Correct 5 ms 348 KB Output is correct
99 Execution timed out 3071 ms 7076 KB Time limit exceeded
100 Halted 0 ms 0 KB -