oj.uz

답안 #1116587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1116587 2024-11-21T21:05:15 Z lucascgar Alternating Current (BOI18_alternating) C++17
19 / 100
 85 ms 13820 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 (!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);
        }
    }

    pii want = {-1,-1};
    for (auto &x:valid) if (x.second){
        want = x.first;
        break;
    }

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

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

            if (l<=r) cyd=cb[bn[i]].second;
            else cyd=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;
    }

    // for (auto &x:bn) cerr << x << '\n';

    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{
        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:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         for (int i=0;i<bn.size();i++){
      |                      ~^~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 22.0

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

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 13296 KB Output is correct
2 Correct 4 ms 6224 KB Output is correct
3 Correct 13 ms 10248 KB Output is correct
4 Correct 24 ms 12720 KB Output is correct
5 Correct 55 ms 13412 KB Output is correct
6 Correct 40 ms 12284 KB Output is correct
7 Correct 50 ms 13052 KB Output is correct
8 Correct 5 ms 6736 KB Output is correct
9 Correct 4 ms 6480 KB Output is correct
10 Correct 71 ms 13772 KB Output is correct
11 Correct 47 ms 12284 KB Output is correct
12 Correct 44 ms 13256 KB Output is correct
13 Correct 3 ms 6224 KB Output is correct
14 Correct 3 ms 6224 KB Output is correct
15 Correct 42 ms 11260 KB Output is correct
16 Correct 30 ms 12808 KB Output is correct
17 Correct 85 ms 13820 KB Output is correct
18 Correct 76 ms 11588 KB Output is correct
19 Correct 4 ms 6736 KB Output is correct
20 Correct 34 ms 11388 KB Output is correct

Subtask #5
0 / 26.0

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