제출 #1117000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117000		lucascgar	Alternating Current (BOI18_alternating)	C++17	100 / 100	112 ms	15804 KiB

alternating

#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});
                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;

    // lst do 1 (ciclo/cara linear que começa no 1 com maior direita)
    if (!f[1][0].empty()){
        lst=-1;
        for (auto &u:f[1][0]) if(ind[u]){
            if (lst==-1 || cb[u].second>cb[lst].second) lst=u;
        }
    }

    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);
            if (i!=1) 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();
    if (!ruim){
        ty[bn[0]]=1;
        for (int i=1;i<sz;i++) ty[bn[i]] = !ty[bn[i-1]];
    }
    else{  // se deu ruim (qnt ímpar de caras bons e ciclo)
        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){
                if (i==0){
                    want = {sz-1, 0};
                }else want = {i-1, i};
                break;
            }

        }

        if (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;
        }


        bool color = 1;

        if (want.first == 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 (auto &x:bn) cerr << cb[x].first << ' ' << cb[x].second << '\n';




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

컴파일 시 표준 에러 (stderr) 메시지

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: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26