oj.uz

답안 #581300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581300 2022-06-22T12:55:00 Z Lobo Alternating Current (BOI18_alternating) C++17
0 / 100
 90 ms 9924 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(m!=2 && m!=5) {
            // for(int i = 0; i < m; i++) cout << n<<"-"<<vec[i].sc<< "--"; 
        }
        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

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: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]
  179 |                 for(int j = i+1; 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:211: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]
  211 |                 for(int j = 0; 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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 1 ms 340 KB no wires in direction 0 between segments 1 and 1
20 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 1 ms 340 KB no wires in direction 0 between segments 1 and 1
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 1 ms 340 KB no wires in direction 0 between segments 1 and 1
20 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 9924 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 21 ms 5524 KB Output is correct
4 Correct 24 ms 5684 KB Output is correct
5 Correct 76 ms 9684 KB Output is correct
6 Correct 81 ms 9676 KB Output is correct
7 Correct 76 ms 9812 KB Output is correct
8 Correct 3 ms 2268 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 77 ms 9904 KB Output is correct
11 Correct 66 ms 9732 KB Output is correct
12 Correct 59 ms 9696 KB Output is correct
13 Correct 2 ms 1876 KB Output is correct
14 Correct 2 ms 1920 KB Output is correct
15 Incorrect 90 ms 9740 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 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 1 ms 340 KB no wires in direction 0 between segments 1 and 1
20 Halted 0 ms 0 KB -