Submission #581353

#	Time	Username	Problem	Language	Result	Execution time	Memory
581353		Lobo	Alternating Current (BOI18_alternating)	C++17	0 / 100	46 ms	10016 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], bit[maxn];

void att(int pos) {
    for(int i = pos; i <= 2*n; i+= i&-i) bit[i]++;
}

int qrr(int pos) {
    int val = 0;
    for(int i = pos; i > 0; i-=i&-i) val+= bit[i];
    return val;
}
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));
        }
    }
    // cout << n<<"-"<<m<<"--";
    // for(auto x : vec) cout << x.fr<<"-"<<x.sc<<"---";

    sort(all(segs),cmp); //menor L, maior R
    for(auto X : segs) {
        int l = X.fr.fr;
        int r = X.fr.sc;
        int id = X.sc;

        if(qrr(2*n-r+1) > 0) {
            pai[id] = -1;
        }
        att(2*n-r+1);
    }

    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.begin()) {
            it--;
            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.begin()) {
            it--;
            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;
            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;

    }

}

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:67:13: warning: unused variable 'l' [-Wunused-variable]
   67 |         int l = X.fr.fr;
      |             ^
alternating.cpp:141: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]
  141 |         for(int i = 0; i < segs.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
alternating.cpp:163: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]
  163 |         for(int i = 0; i+1 < segs.size(); i++) {
      |                        ~~~~^~~~~~~~~~~~~
alternating.cpp:181: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]
  181 |                 for(int j = i+1; j < segs.size(); j++) {
      |                                  ~~^~~~~~~~~~~~~
alternating.cpp:164:17: warning: unused variable 'l1' [-Wunused-variable]
  164 |             int l1 = segs[i].fr.fr;
      |                 ^~
alternating.cpp:167:17: warning: unused variable 'r2' [-Wunused-variable]
  167 |             int r2 = segs[i+1].fr.sc;
      |                 ^~
alternating.cpp:213: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]
  213 |                 for(int j = 0; j < segs.size(); j++) {
      |                                ~~^~~~~~~~~~~~~
alternating.cpp:198:17: warning: unused variable 'l1' [-Wunused-variable]
  198 |             int l1 = segs.back().fr.fr;
      |                 ^~
alternating.cpp:201:17: warning: unused variable 'r2' [-Wunused-variable]
  201 |             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