Submission #581284

#	Time	Username	Problem	Language	Result	Execution time	Memory
581284		Lobo	Alternating Current (BOI18_alternating)	C++17	0 / 100	46 ms	10176 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;
        }
        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));
        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));
        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;
    }

    for(auto x : segs) {
        // cout << x.fr.fr << " " << x.fr.sc << " " << x.sc << endl;
    }
    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(m!=2 && m!=5) {
            for(int i = 0; i < m; i++) cout << i<<"-"<<pai[i]<< " "; 
        }
        if(segs.size() == 1) {
            ans[segs[0].sc] = 1;
            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; 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;
                int i = 0;
                for(int j = i; 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;
            }
 
        }
        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;

    }

}

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:111:9: warning: left operand of comma operator has no effect [-Wunused-value]
  111 |         l2,r2,id;
      |         ^~
alternating.cpp:111:15: warning: right operand of comma operator has no effect [-Wunused-value]
  111 |         l2,r2,id;
      |               ^~
alternating.cpp:111:17: warning: right operand of comma operator has no effect [-Wunused-value]
  111 |         l2,r2,id;
      |                 ^
alternating.cpp:132:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  132 |     for(auto x : segs) {
      |              ^
alternating.cpp:136: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]
  136 |         for(int i = 0; i < segs.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
alternating.cpp:161: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]
  161 |         for(int i = 0; i+1 < segs.size(); i++) {
      |                        ~~~~^~~~~~~~~~~~~
alternating.cpp:179: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]
  179 |                 for(int j = i; j < segs.size(); j++) {
      |                                ~~^~~~~~~~~~~~~
alternating.cpp:162:17: warning: unused variable 'l1' [-Wunused-variable]
  162 |             int l1 = segs[i].fr.fr;
      |                 ^~
alternating.cpp:165:17: warning: unused variable 'r2' [-Wunused-variable]
  165 |             int r2 = segs[i+1].fr.sc;
      |                 ^~
alternating.cpp:212: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]
  212 |                 for(int j = i; j < segs.size(); j++) {
      |                                ~~^~~~~~~~~~~~~
alternating.cpp:196:17: warning: unused variable 'l1' [-Wunused-variable]
  196 |             int l1 = segs.back().fr.fr;
      |                 ^~
alternating.cpp:199:17: warning: unused variable 'r2' [-Wunused-variable]
  199 |             int r2 = segs[0].fr.sc+n;
      |                 ^~

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