Submission #581337

#	Time	Username	Problem	Language	Result	Execution time	Memory
581337		Lobo	Alternating Current (BOI18_alternating)	C++17	55 / 100	84 ms	13108 KiB

alternating

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, m, pai[maxn], ps[maxn], ans[maxn];

int find(int v) {
    if(pai[v] == v) return v;
    return pai[v] = find(pai[v]);
}

bool cmp(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
    if(a.fr.fr == b.fr.fr) {
        return a.fr.sc > b.fr.sc;
    }
    return a.fr.fr < b.fr.fr;
}

void solve() {
    cin >> n >> m;
    vector<pair<pair<int,int>,int>> segs;
    vector<pair<int,int>> vec;
    for(int i = 0; i < m; i++) {
        int a,b; cin >> a >> b;
        vec.pb(mp(a,b));
        pai[i] = i;
        if(b >= a) {
            ps[a]++;
            ps[b+1]--;
            ps[a+n]++;
            ps[b+n+1]--;

            segs.pb(mp(mp(a,b),i));
            segs.pb(mp(mp(a+n,b+n),i));
        }
        else {
            ps[a]++;
            ps[b+n+1]--;
            ps[1]++;
            ps[b+1]--;
            ps[a+n]++;
            ps[2*n+1]--;
            segs.pb(mp(mp(a,b+n),i));
        }
    }

    sort(all(segs),cmp); //menor L, maior R
    priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int>>,greater<pair<pair<int,int>,int>>> pq;
    for(auto X : segs) {
        int l = X.fr.fr;
        int r = X.fr.sc;
        int id = X.sc;
        // cout << l << " " << r << " -" << id << endl;
        while(pq.size() && pq.top().fr.sc < r) pq.pop();
        if(pq.size() && pq.top().fr.fr <= l) {
            pai[id] = pq.top().sc;
            // cout << " " << pai[id] << endl;
        }
        else {
            pq.push(mp(mp(l,r),id));
        }
    }

    segs.clear();
    for(int i = 0; i < m; i++) {
        // cout << i << " " << pai[i] << endl;
        if(pai[i] == i) {
            int a = vec[i].fr;
            int b = vec[i].sc;
            if(b >= a) {
                segs.pb(mp(mp(a,b),i));
            }
            else {
                segs.pb(mp(mp(a,b+n),i));
            }
        }
    }
    sort(all(segs));

    for(int i = 0; i < m; i++) {
        if(pai[i] == i) continue;
        int l1 = vec[i].fr;
        int r1 = vec[i].sc;
        //ve o ultimo com l menor ou igual a l1
        auto it = lower_bound(all(segs),mp(mp(l1,inf),0LL));
        if(it != segs.end()) {
            int l2,r2,id;
            l2 = it->fr.fr;
            r2 = it->fr.sc;
            id = it->sc;
            //ve se da certo com esse
            if(l1 >= l2 && r1 <= r2) {
                pai[i] = id;
                continue;
            }
        }

        //tenta com l1+n e r1+n
        l1+= n;
        r1+= n;
        it = lower_bound(all(segs),mp(mp(l1,inf),0LL));
        if(it != segs.end()) {
            int l2,r2,id;
            l2 = it->fr.fr;
            r2 = it->fr.sc;
            id = it->sc;
            //ve se da certo com esse
            if(l1 >= l2 && r1 <= r2) {
                pai[i] = id;
                continue;
            }
        }
    }

    bool ok = true;
    for(int i = 1; i <= 2*n; i++) {
        ps[i]+=ps[i-1];
        if(ps[i] < 2) ok = false;
    }
    if(!ok) {
        cout << "impossible" << endl;
        return;
    }

    if((((int) segs.size())&1) == 0) {
        for(int i = 0; i < segs.size(); i++) {
            int id = segs[i].sc;
            ans[id] = i&1;
        }
        for(int i = 0; i < m; i++) {
            if(pai[i] == i) continue;
            ans[i] = ans[pai[i]]^1;
        }

        for(int i = 0; i < m; i++) {
            cout << ans[i];
        }cout << endl;
    }
    else {
        if(segs.size() == 1) {
            ans[segs[0].sc] = 1;

            int ps0[maxn], ps1[maxn];
            for(int i = 0; i <= n; i++) {
                ps0[i] = ps1[0] = 0;
            }
            for(auto x : segs) {
                // cout << x.fr.fr << " " << x.fr.sc << " " << x.sc << endl;
            }

            for(int i = 0; i < m; i++) {
                // cout << i << " -> " << vec[pai[i]].fr << " " << vec[pai[i]].sc << endl;
                int a = vec[i].fr;
                int b = vec[i].sc;
                if(b >= a) {
                    if(ans[i] == 0) {
                        ps0[a]++;
                        ps0[b+1]--;
                    }
                    else {
                        ps1[a]++;
                        ps1[b+1]--;
                    }
                }
                else {
                    if(ans[i] == 0) {
                        ps0[b]++;
                        ps0[1]++;
                        ps0[a+1]--;
                    }
                    else {
                        ps1[b]++;
                        ps1[1]++;
                        ps1[a+1]--;
                    }
                }
            }

            bool okk = false;
            for(int i = 1; i <= n; i++) {
                ps0[i]+= ps0[i-1];
                ps1[i]+= ps1[i-1];
                if(ps0[i] == 0 || ps1[i] == 0) {
                    okk = true;
                }
            }
            if(okk) {
                cout << n<<"--"<<m<<"---";
                cout << segs[0].fr.fr<<"--"<<segs[0].fr.sc;
                return;
            }

            for(int i = 0; i < m; i++) {
                cout << ans[i];
            }cout << endl;
            return;
        }
        bool ok = false;
        for(int i = 0; i+1 < segs.size(); i++) {
            int l1 = segs[i].fr.fr;
            int r1 = segs[i].fr.sc;
            int l2 = segs[i+1].fr.fr;
            int r2 = segs[i+1].fr.sc;

            //a area coberta por dois é l2 até r1
            int l = l2;
            int r = r1;
            bool ok1 = true;
            for(int i = l; i <= r; i++) {
                if(ps[i] < 3) {
                    ok1 = false;
                    break;
                }
            }
            if(ok1) {
                int cnt = 0;
                for(int j = i+1; j < segs.size(); j++) {
                    int id = segs[j].sc;
                    ans[id]=cnt;
                    cnt^=1;
                }
                for(int j = 0; j <= i; j++) {
                    int id = segs[j].sc;
                    ans[id]=cnt;
                    cnt^=1;
                }
                ok = true;
                break;
            }
        }

        if(ok == false) {
            //ultimo com o primeiro
            int l1 = segs.back().fr.fr;
            int r1 = segs.back().fr.sc;
            int l2 = segs[0].fr.fr+n;
            int r2 = segs[0].fr.sc+n;
            int l = l2;
            int r = r1;
            bool ok1 = true;
            for(int i = l; i <= r; i++) {
                if(ps[i] < 3) {
                    ok1 = false;
                    break;
                }
            }
            if(ok1) {
                int cnt = 0;
                for(int j = 0; j < segs.size(); j++) {
                    int id = segs[j].sc;
                    ans[id]=cnt;
                    cnt^=1;
                }
                ok = true;
            }
 
        }
        if(ok == false) {
            cout << "impossible" << endl;
            return;
        }
        for(int i = 0; i < m; i++) {
            if(pai[i] == i) continue;
            ans[i] = ans[pai[i]]^1;
        }
        for(int i = 0; i < m; i++) {
            cout << ans[i];
        }cout << endl;

    }






    int ps0[maxn], ps1[maxn];
    for(int i = 0; i <= n; i++) {
        ps0[i] = ps1[0] = 0;
    }
    for(auto x : segs) {
        // cout << x.fr.fr << " " << x.fr.sc << " " << x.sc << endl;
    }

    for(int i = 0; i < m; i++) {
        // cout << i << " -> " << vec[pai[i]].fr << " " << vec[pai[i]].sc << endl;
        int a = vec[i].fr;
        int b = vec[i].sc;
        if(b >= a) {
            if(ans[i] == 0) {
                ps0[a]++;
                ps0[b+1]--;
            }
            else {
                ps1[a]++;
                ps1[b+1]--;
            }
        }
        else {
            if(ans[i] == 0) {
                ps0[b]++;
                ps0[1]++;
                ps0[a+1]--;
            }
            else {
                ps1[b]++;
                ps1[1]++;
                ps1[a+1]--;
            }
        }
    }

    bool okk = false;
    for(int i = 1; i <= n; i++) {
        ps0[i]+= ps0[i-1];
        ps1[i]+= ps1[i-1];
        if(ps0[i] == 0 || ps1[i] == 0) {
            okk = true;
        }
    }
    if(okk) {
        cout << "penis";
    }cout << endl;

}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message (stderr)

alternating.cpp: In function 'void solve()':
alternating.cpp:138:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for(int i = 0; i < segs.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
alternating.cpp:159:22: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  159 |             for(auto x : segs) {
      |                      ^
alternating.cpp:211:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |         for(int i = 0; i+1 < segs.size(); i++) {
      |                        ~~~~^~~~~~~~~~~~~
alternating.cpp:229:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |                 for(int j = i+1; j < segs.size(); j++) {
      |                                  ~~^~~~~~~~~~~~~
alternating.cpp:212:17: warning: unused variable 'l1' [-Wunused-variable]
  212 |             int l1 = segs[i].fr.fr;
      |                 ^~
alternating.cpp:215:17: warning: unused variable 'r2' [-Wunused-variable]
  215 |             int r2 = segs[i+1].fr.sc;
      |                 ^~
alternating.cpp:261:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  261 |                 for(int j = 0; j < segs.size(); j++) {
      |                                ~~^~~~~~~~~~~~~
alternating.cpp:246:17: warning: unused variable 'l1' [-Wunused-variable]
  246 |             int l1 = segs.back().fr.fr;
      |                 ^~
alternating.cpp:249:17: warning: unused variable 'r2' [-Wunused-variable]
  249 |             int r2 = segs[0].fr.sc+n;
      |                 ^~
alternating.cpp:293:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  293 |     for(auto x : segs) {
      |              ^

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