oj.uz

Submission #721091

# Submission time Handle Problem Language Result Execution time Memory
721091 2023-04-10T10:04:58 Z Magikarp4000 Alternating Current (BOI18_alternating) C++17
0 / 100
 3000 ms 5756 KB 
#include <bits/stdc++.h>
using namespace std;
#define INF int(1e9+7)
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define ln '\n'
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define ALL(v) v.begin(), v.end()
#define PB push_back
#define F first
#define S second
const ll LLINF = 1e18+1;

struct Wire {
    int l,r,idx;
};

const int MAXN = 1e5+1;
int n,m;
PII p[MAXN], q[MAXN];
bool res[MAXN], z[MAXN];
vector<Wire> pro,noob;
int pn,nn;
int w[MAXN];

bool cmp(const Wire& x, const Wire& y) {
    return x.l < y.l;
}

bool check(int k) {
    vector<PII> a,b;
    vector<int> dir(m,0);
    FOR(i,0,m) res[i] = 0;
    FOR(i,0,pn) {
        if ((i+k)%2 == 0) {
            a.PB(q[pro[(i+k)%pn].idx]);
            dir[pro[i].idx] = 0;
        }
        else {
            b.PB(q[pro[(i+k)%pn].idx]);
            dir[pro[i].idx] = 1;
            res[pro[i].idx] = 1;
        }
    }
    FOR(i,0,nn) {
        if (dir[w[noob[i].idx]] == 0) {
            b.PB(q[noob[i].idx]);
            res[noob[i].idx] = 1;
        }
        else a.PB(q[noob[i].idx]);
    }
    a.clear(); b.clear();
    FOR(i,0,n) {
        if (res[i] == 0) a.PB(q[i]);
        else b.PB(q[i]);
    }
    sort(ALL(a));
    sort(ALL(b));
    // FORX(u,a) cout << u.F << ' ';
    // cout << ln;
    // FORX(u,b) cout << u.F << ' ';
    // cout << ln;
    // cout << ln;
    int pos = a[0].S, idx = 0;
    while (idx < a.size() && pos < a[0].F+n-1) {
        if (a[idx].F > pos+1) return 0;
        pos = max(pos,a[idx].S);
        idx++;
    }
    if (pos < a[0].F+n-1) return 0;
    pos = b[0].S, idx = 0;
    while (idx < b.size() && pos < b[0].F+n-1) {
        if (b[idx].F > pos+1) return 0;
        pos = max(pos,b[idx].S);
        idx++;
    }
    if (pos < b[0].F+n-1) return 0;
    return 1;
}

signed main() {
    cin >> n >> m;
    FOR(i,0,m) cin >> p[i].F >> p[i].S;
    FOR(i,0,m) {
        q[i].F = p[i].F;
        q[i].S = p[i].S < p[i].F ? p[i].S+n : p[i].S;
    }
    FOR(i,0,m) {
        if (z[i]) continue;
        FOR(j,0,m) {
            if (i == j) continue;
            if ((q[i].F <= q[j].F && q[i].S >= q[j].S) || 
            ((p[i].S%n) == p[i].F-1) || 
            (p[j].S >= p[j].F && q[i].F <= p[j].F+n && q[i].S >= p[j].S+n)) {
                z[j] = 1;
                w[j] = i;
            }
        }
    }
    FOR(i,0,m) {
        if (!z[i]) pro.PB({q[i].F,q[i].S,i});
        else noob.PB({q[i].F,q[i].S,i});
    }
    sort(ALL(pro),cmp);
    sort(ALL(noob),cmp);
    // FORX(u,pro) cout << u.idx << ' ';
    // cout << ln;
    // FORX(u,noob) cout << u.idx << ' ';
    // cout << ln;
    pn = pro.size(), nn = noob.size();
    FOR(i,0,pn) {
        // FOR(j,0,pn) {
        //     if ((j+i)%2 == 0) cout << (i+j)%pn;
        // }
        // cout << ln;
        // FOR(j,0,pn) {
        //     if ((j+i)%2 == 1) cout << (i+j)%pn;
        // }
        // cout << ln << ln;
        if (check(i)) {
            FOR(j,0,m) cout << res[j];
            return 0;
        }
    }
    cout << "impossible";
}

Compilation message

alternating.cpp: In function 'bool check(int)':
alternating.cpp:68:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     while (idx < a.size() && pos < a[0].F+n-1) {
      |            ~~~~^~~~~~~~~~
alternating.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     while (idx < b.size() && pos < b[0].F+n-1) {
      |            ~~~~^~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5756 KB Output is correct
2 Correct 3 ms 1484 KB Output is correct
3 Correct 31 ms 3416 KB Output is correct
4 Correct 34 ms 3352 KB Output is correct
5 Execution timed out 3080 ms 2296 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -