oj.uz

답안 #581282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581282 2022-06-22T12:45:49 Z Lobo Alternating Current (BOI18_alternating) C++17
0 / 100
 76 ms 10028 KB 
#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(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

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:158: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]
  158 |         for(int i = 0; i+1 < segs.size(); i++) {
      |                        ~~~~^~~~~~~~~~~~~
alternating.cpp:176: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]
  176 |                 for(int j = i; j < segs.size(); j++) {
      |                                ~~^~~~~~~~~~~~~
alternating.cpp:159:17: warning: unused variable 'l1' [-Wunused-variable]
  159 |             int l1 = segs[i].fr.fr;
      |                 ^~
alternating.cpp:162:17: warning: unused variable 'r2' [-Wunused-variable]
  162 |             int r2 = segs[i+1].fr.sc;
      |                 ^~
alternating.cpp:209: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]
  209 |                 for(int j = i; j < segs.size(); j++) {
      |                                ~~^~~~~~~~~~~~~
alternating.cpp:193:17: warning: unused variable 'l1' [-Wunused-variable]
  193 |             int l1 = segs.back().fr.fr;
      |                 ^~
alternating.cpp:196:17: warning: unused variable 'r2' [-Wunused-variable]
  196 |             int r2 = segs[0].fr.sc+n;
      |                 ^~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 340 KB no wires in direction 1 between segments 12 and 13
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 340 KB no wires in direction 1 between segments 12 and 13
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 340 KB no wires in direction 1 between segments 12 and 13
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 10028 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 23 ms 5592 KB Output is correct
4 Correct 25 ms 5632 KB Output is correct
5 Correct 74 ms 9812 KB Output is correct
6 Correct 74 ms 9716 KB Output is correct
7 Correct 71 ms 9720 KB Output is correct
8 Correct 5 ms 2224 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 76 ms 9904 KB Output is correct
11 Correct 62 ms 9812 KB Output is correct
12 Correct 60 ms 9784 KB Output is correct
13 Correct 2 ms 1876 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Incorrect 62 ms 9812 KB no wires in direction 1 between segments 1 and 1
16 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 340 KB no wires in direction 1 between segments 12 and 13
5 Halted 0 ms 0 KB -