Submission #1036796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036796		anango	Alternating Current (BOI18_alternating)	C++17	55 / 100	3071 ms	7076 KiB

alternating

#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 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26