Submission #984560

#	Time	Username	Problem	Language	Result	Execution time	Memory
984560		Ahmed57	Alternating Current (BOI18_alternating)	C++17	100 / 100	76 ms	16264 KiB

alternating

#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,m;cin>>n>>m;
    int pref[n+2] = {0};
    vector<array<int,3>> v;
    vector<array<int,2>> rng[n+1];
    int dir[m+1] = {0};
    int ma = -1, lol = -1;
    int mi = 1e9;
    set<int> s;
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        if(a<=b){
            pref[a]++;
            pref[b+1]--;
        }else{
            pref[a]++;
            pref[1]++;
            pref[b+1]--;
            b+=n;
        }
        v.push_back({a,b,i});
        rng[a].push_back({b,i});
        s.insert(a);
    }    
    vector<int> roro;
    for(auto i:s){
        int ma = -1;
        int lol = 0;
        for(auto j:rng[i]){
            if(ma<j[0]){
                ma = j[0];
                lol = j[1];
            }
        }
        roro.push_back(lol);
    }
    for(int i = 2;i<=n;i++){
        pref[i]+=pref[i-1];
    }
    for(int i = 1;i<=n;i++){
        if(pref[i]<=1){
            cout<<"impossible\n";
            return 0;
        }
    }
    for(auto i:roro){
        for(int j = 0;j<m;j++)dir[j] = 0;
        int ind = v[i][0];
        int nah = v[i][1], fe = v[i][2];
        bool bad = 0;
        while(ind<v[i][0]+n){
            if(ind-1==nah){
                bad = 1;
                break;
            }
            if(nah==-1){
                bad = 1;
                break;
            }
            int er = nah;
            dir[fe] = 1;
            if(er>=v[i][0]+n){
                break;
            }
            while(ind<=er){
                ind++;
                for(auto j:rng[(ind-1)%n+1]){
                    if(nah<(j[0]>n?j[0]:(ind<=n?j[0]:j[0]+n))){
                        nah = (j[0]>n?j[0]:(ind<=n?j[0]:j[0]+n));
                        fe = j[1];
                    }
                }
                if(ind<=er&&pref[(ind-1)%n+1]==2)nah = -1;
            }
        }
        int npref[n+2];
        for(int j = 1;j<=n;j++){
            npref[j] = 0;
        }
        for(int j = 0;j<m;j++){
            if(dir[j])continue;
            if(v[j][1]>n){
                npref[v[j][0]]++;
                npref[1]++;
                npref[(v[j][1]-1)%n+2]--;
            }else{
                npref[v[j][0]]++;
                npref[v[j][1]+1]--;
            }
        }
        for(int j = 2;j<=n;j++)npref[j]+=npref[j-1];
        for(int j = 1;j<=n;j++){
            if(npref[j]==0){
                bad = 1;
                break;
            }
        }
        if(bad==0){
            for(int j = 0;j<m;j++){
                cout<<dir[j];
            }
            return 0;
        }
    }
    cout<<"impossible\n";
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:13:9: warning: unused variable 'ma' [-Wunused-variable]
   13 |     int ma = -1, lol = -1;
      |         ^~
alternating.cpp:13:18: warning: unused variable 'lol' [-Wunused-variable]
   13 |     int ma = -1, lol = -1;
      |                  ^~~
alternating.cpp:14:9: warning: unused variable 'mi' [-Wunused-variable]
   14 |     int mi = 1e9;
      |         ^~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26