oj.uz

답안 #1116593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1116593 2024-11-21T21:35:52 Z lucascgar Alternating Current (BOI18_alternating) C++17
19 / 100
 92 ms 13564 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]; // 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});
                f[1][0].push_back(i);
                f[b][1].push_back(i);
                f[a][0].push_back(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;
        }
    }

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

    set<int> all, im;
    vector<int> bn;  // bons (ciclos aparecem só no final)
    int lst=0;
    map<pii, bool> valid;
    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
        }

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

        if (im.size()==2){
            pii srch = {*im.begin(), *next(im.begin())};
            if (!valid.count(srch)) valid[srch] = 1;
            if (all.empty()) valid[srch] = 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};
    for (auto &x:valid) if (x.second){
        want = x.first;
        break;
    }

    if (ruim && want.first==-1){  // pegar não-interseção
        lst = bn.back();
        for (int i=0;i<sz;i++){
            int l = cb[bn[i]].first, r=cb[bn[i]].second;

            if (l>cb[lst].second){
                want = {lst, bn[i]};
                // cerr << bn[i] << ' ' << lst << ' ' << " for " << cyd << '\n';
                break;
            }
            if (l>r) break;
            lst = bn[i];
        }
    }

    // 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:69:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |     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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 4 ms 4944 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 4 ms 4944 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 4 ms 4944 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 13048 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 14 ms 9224 KB Output is correct
4 Correct 26 ms 11784 KB Output is correct
5 Correct 56 ms 13296 KB Output is correct
6 Correct 48 ms 11980 KB Output is correct
7 Correct 42 ms 12796 KB Output is correct
8 Correct 6 ms 5456 KB Output is correct
9 Correct 4 ms 5200 KB Output is correct
10 Correct 52 ms 13520 KB Output is correct
11 Correct 41 ms 11740 KB Output is correct
12 Correct 43 ms 12804 KB Output is correct
13 Correct 4 ms 4944 KB Output is correct
14 Correct 4 ms 5172 KB Output is correct
15 Correct 51 ms 11144 KB Output is correct
16 Correct 26 ms 12040 KB Output is correct
17 Correct 92 ms 13564 KB Output is correct
18 Correct 86 ms 11124 KB Output is correct
19 Correct 6 ms 5456 KB Output is correct
20 Correct 35 ms 11244 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 4 ms 4944 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -