Submission #580845

#	Time	Username	Problem	Language	Result	Execution time	Memory
580845		Lobo	Alternating Current (BOI18_alternating)	C++17	0 / 100	43 ms	10024 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];

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;
    if(m == 2) {
        int l1,r1; cin >> l1 >> r1;
        int l2,r2; cin >> l2 >> r2;
        int cnt = 0;
        if(l1 == 1 && r1 == n || l1 == r1+1) cnt++;
        if(l2 == 1 && r2 == n || l2 == r2+1) cnt++;
        if(cnt == 2) {
            cout << "01" << endl;
        }
        else {
            cout << "impossible" << endl;
        }
        return;
    }
    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] = -1;
        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++) {
        if(pai[i] == -1) {
            segs.pb(mp(vec[i],i));
        }
    }
    sort(all(segs));

    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 << 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] == -1) continue;
            ans[i] = ans[pai[i]]^1;
        }

        for(int i = 0; i < m; i++) {
            cout << ans[i];
        }cout << endl;
    }
    else {
        bool ok = false;
        for(int i = 0; i < segs.size(); i++) {
            int l1 = segs[i].fr.fr;
            int r1 = segs[i].fr.sc;
            int l2 = segs[(i+1)%((int)segs.size())].fr.fr;
            int r2 = segs[(i+1)%((int)segs.size())].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;
            }
        }
        
            cout << "impossible" << endl;
        // if(ok == false) {
        //     cout << "impossible" << endl;
        //     return;
        // }
        // for(int i = 0; i < m; i++) {
        //     if(pai[i] == -1) 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:32:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   32 |         if(l1 == 1 && r1 == n || l1 == r1+1) cnt++;
      |            ~~~~~~~~^~~~~~~~~~
alternating.cpp:33:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   33 |         if(l2 == 1 && r2 == n || l2 == r2+1) cnt++;
      |            ~~~~~~~~^~~~~~~~~~
alternating.cpp:102:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  102 |     for(auto x : segs) {
      |              ^
alternating.cpp:106: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]
  106 |         for(int i = 0; i < segs.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
alternating.cpp:121: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]
  121 |         for(int i = 0; i < segs.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
alternating.cpp:139: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]
  139 |                 for(int j = i; j < segs.size(); j++) {
      |                                ~~^~~~~~~~~~~~~
alternating.cpp:122:17: warning: unused variable 'l1' [-Wunused-variable]
  122 |             int l1 = segs[i].fr.fr;
      |                 ^~
alternating.cpp:125:17: warning: unused variable 'r2' [-Wunused-variable]
  125 |             int r2 = segs[(i+1)%((int)segs.size())].fr.sc;
      |                 ^~
alternating.cpp:120:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  120 |         bool ok = false;
      |              ^~

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