oj.uz

Submission #1116742

# Submission time Handle Problem Language Result Execution time Memory
1116742 2024-11-22T09:27:39 Z lucascgar Alternating Current (BOI18_alternating) C++17
19 / 100
 88 ms 14596 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
/*
se p dois intervalos [a,b] a cobre b, ent a e b tem que ter tipos diferentes
resposta válida tem que ter alguem que cobre outro
ignorar os cobertos
pensar no círculo
vendo os independentes posso colocar eles de cores diferentes pra aproveitar interseções
parte com eles sozinhos tem que ter intervalos contidos bons
qnt par deles fechou
*/
 
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
 
const int MAXN = 1e5+10;
 
vector<int> f[MAXN][2]; // {start, end} fios
pii cb[MAXN];
bool ty[MAXN];
bool ind[MAXN], iscy[MAXN];  // se é independente, ciclo

int pai[MAXN], qnt[MAXN]; // pros ruins, quem contem ele

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout << fixed << setprecision(7);

    int n, m;
    cin >> n >> m;
 
    int a, b, cyd=0, cyl=1e9+1;

    vector<pair<pii, int>> ord, cy;

    for (int i=0;i<m;i++){
        cin >> a >> b;
        cb[i] = {a,b}, pai[i]=-1;
        if(b<a){
            if (b==a-1){
                a=1,b=n;
                cb[i]={a,b};
            }else{
                cyd = max(cyd, b), cyl = min(cyl, a), iscy[i]=1;
                cy.push_back({{a,-b}, i});
                continue;
            }
        }
        ord.push_back({{a,-b}, i});
        f[a][0].push_back(i);
        f[b][1].push_back(i);
    }
    if (!ord.empty()) sort(ord.begin(), ord.end());
    bool ruim = 0;
    for (auto &x:ord){
        x.first.second = -x.first.second;
        if (x.first.second <= cyd) continue;
        if (x.first.first >= cyl) break;
        cyd = x.first.second, ind[x.second]=1, ruim^=1;
    }

    if (cy.empty() || !ord.empty() && ord[0].first.first == 1 && ord[0].first.second==n) ruim=0;  // se tem um cara que cobre todo mundo ou nn tem ciclos
    else{  // ver ciclos
        sort(cy.begin(), cy.end());
        cyd = 0;
        for (auto &x:cy){
            x.first.second*=-1;
            if (x.first.second<=cyd) continue;
            cyd=x.first.second, ind[x.second]=1, ruim^=1;
        }
    }

    for (auto &[_, i]:cy){  // colocar ciclos na ordem certa
        a = cb[i].first, b = cb[i].second;
        f[1][0].push_back(i);
        f[b][1].push_back(i);
        f[a][0].push_back(i);
    }

    ord.clear();
    cy.clear();

    set<int> all, im;
    vector<int> bn;  // bons (ciclos aparecem só no final)
    int lst=0;

    for (int i=1;i<=n;i++){
        for (auto &u:f[i][0]) if (ind[u]){
            if (!iscy[u] || i>=cyl) bn.push_back(u);
            im.insert(u);
            lst = u;
        }
        while (!f[i][0].empty()){
            int u = f[i][0].back();
            f[i][0].pop_back();
            if (ind[u]) continue;
            all.insert(u);
            pai[u] = lst;  // se um ruim cobre um trecho sem importantes ent ele deveria ser importante
        }

        qnt[i]=all.size()+im.size();
        if (qnt[i]<2){
            cout << "impossible\n";
            return 0;
        }


        while (!f[i][1].empty()){
            int u = f[i][1].back();
            f[i][1].pop_back();
            if (ind[u]) im.erase(u);
            else all.erase(u);
        }
    }
    int sz = bn.size();

    pii want = {-1,-1};

    lst = bn.back();
    for (int i=0;i<sz;lst=bn[i],i++){
        if (i==0 && !iscy[bn.back()]){
            want = {bn[i],lst};
            break;
        }
        int x = bn[i];
        bool vld = 1;
        int l = cb[x].first, r = cb[lst].second;
        // cerr << lst << ' ' << x << ": " << l << '-' << r << '\n';
        if (l<=r){
            for (int j=l;j<=r;j++){
                if (qnt[j]-1 < 2){
                    vld=0;
                    break;
                }
            }
        }else if(iscy[x] && iscy[lst]){
            for (int j=l;j<=n;j++){
                if (qnt[j]-1 < 2){
                    vld=0;
                    break;
                }
            }
            for (int j=1;j<=r;j++){
                if (qnt[j]-1 < 2){
                    vld=0;
                    break;
                }    
            }
        }

        if (vld){
            want = {x, lst};
            break;
        }

    }

    // for (auto &x:bn) cerr << cb[x].first << ' ' << cb[x].second << '\n';

    if (ruim && want.first==-1){  // quantidade é ímpar e não tem uma interseção que é válida nem um cara que cobre todo mundo
        cout << "impossible\n";
        return 0;
    }


    if (!ruim){
        ty[bn[0]]=1;
        for (int i=1;i<sz;i++) ty[bn[i]] = !ty[bn[i-1]];
    }else{
        for (int i=0;i<sz;i++){
            if (bn[i]==want.first) want.first = m+i;
            else if (bn[i]==want.second) want.second=m+i;
        }
        want.first-=m, want.second-=m;
        if (want.second<want.first) swap(want.first, want.second);
        bool color = 1;

        if (want == ((pii){0,sz-1})){
            for (int i=0;i<sz;i++){
                ty[bn[i]] = color, color=!color;
            }
        }else{
            for (int i=want.second;i<sz;i++){
                ty[bn[i]] = color, color=!color;
            }
            for (int i=0;i<=want.first;i++){
                ty[bn[i]] = color, color=!color;
            }
        }

    }

    for (int i=0;i<m;i++){
        if (pai[i] == -1) cout << ty[i];
        else cout << !ty[pai[i]];
    }
    cout << '\n';
 
    return 0;
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:66:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |     if (cy.empty() || !ord.empty() && ord[0].first.first == 1 && ord[0].first.second==n) ruim=0;  // se tem um cara que cobre todo mundo ou nn tem ciclos
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 2 ms 6852 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6992 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Correct 2 ms 6736 KB Output is correct
7 Correct 2 ms 6736 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Correct 2 ms 6736 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 2 ms 6736 KB Output is correct
13 Correct 2 ms 6736 KB Output is correct
14 Incorrect 2 ms 6736 KB no wires in direction 0 between segments 3 and 7
15 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 2 ms 6852 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6992 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Correct 2 ms 6736 KB Output is correct
7 Correct 2 ms 6736 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Correct 2 ms 6736 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 2 ms 6736 KB Output is correct
13 Correct 2 ms 6736 KB Output is correct
14 Incorrect 2 ms 6736 KB no wires in direction 0 between segments 3 and 7
15 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 2 ms 6852 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6992 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Correct 2 ms 6736 KB Output is correct
7 Correct 2 ms 6736 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Correct 2 ms 6736 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 2 ms 6736 KB Output is correct
13 Correct 2 ms 6736 KB Output is correct
14 Incorrect 2 ms 6736 KB no wires in direction 0 between segments 3 and 7
15 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 13808 KB Output is correct
2 Correct 2 ms 6992 KB Output is correct
3 Correct 13 ms 10420 KB Output is correct
4 Correct 33 ms 12988 KB Output is correct
5 Correct 45 ms 13344 KB Output is correct
6 Correct 40 ms 13052 KB Output is correct
7 Correct 43 ms 14332 KB Output is correct
8 Correct 4 ms 6992 KB Output is correct
9 Correct 3 ms 6992 KB Output is correct
10 Correct 58 ms 14248 KB Output is correct
11 Correct 34 ms 12748 KB Output is correct
12 Correct 38 ms 14596 KB Output is correct
13 Correct 3 ms 6992 KB Output is correct
14 Correct 2 ms 6992 KB Output is correct
15 Correct 39 ms 12400 KB Output is correct
16 Correct 24 ms 13064 KB Output is correct
17 Correct 88 ms 14068 KB Output is correct
18 Correct 80 ms 12284 KB Output is correct
19 Correct 4 ms 7248 KB Output is correct
20 Correct 42 ms 11748 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 2 ms 6852 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6992 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Correct 2 ms 6736 KB Output is correct
7 Correct 2 ms 6736 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Correct 2 ms 6736 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 2 ms 6736 KB Output is correct
13 Correct 2 ms 6736 KB Output is correct
14 Incorrect 2 ms 6736 KB no wires in direction 0 between segments 3 and 7
15 Halted 0 ms 0 KB -