oj.uz

Submission #1111056

# Submission time Handle Problem Language Result Execution time Memory
1111056 2024-11-11T11:36:52 Z Pioneer Sphinx's Riddle (IOI24_sphinx) C++17
36 / 100
 106 ms 496 KB 
#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define sz(s) ((int)s.size())
#define all(v) v.begin(),v.end()

const int MAX=255;

struct dsu{
    int f[MAX];

    void init(int n){
        for(int i=0;i<n;i++)f[i]=i;
    }

    int get(int v){
        return (f[v]==v?v:f[v]=get(f[v]));
    }

    void unite(int a,int b){
        a=get(a),b=get(b);
        f[a]=b;
    }
}d,dd;

int n;
vector<int> g[MAX];

bool bar(int mid,int l,int r){
    vector<int> ask(n,-1);
    for(int i=0;i<mid;i++){
        if(d.get(i)<l||d.get(i)>r){
            ask[i]=n;
        }
    }
    for(int i=mid+1;i<n;i++)ask[i]=n;
    dd.init(n);
    for(int i=0;i<n;i++){
        for(auto to:g[i]){
            if(ask[i]==n&&ask[to]==n){
                dd.unite(i,to);
            }
        }
    }
    for(int i=0;i<mid;i++){
        for(auto to:g[i]){
            if(d.get(i)==d.get(to)){
                dd.unite(i,to);
            }
        }
    }
    vector<int> vec;
    for(int i=0;i<n;i++)vec.pb(dd.get(i));
    sort(all(vec));
    vec.erase(unique(all(vec)),vec.end());
    return (sz(vec)!=perform_experiment(ask));
}

vector<int> g1[MAX];
int dep[MAX];
int use[MAX];
vector<int> ver[2];

void dfs(int v){
    use[v]=1;
    ver[dep[v]].pb(v);
    for(auto to:g1[v]){
        if(use[to])continue;
        dep[to]=(dep[v]^1);
        dfs(to);
    }
}

bool BAR(int l,int r,int color){
    vector<int> ask(n,-1);
    for(int i=0;i<n;i++){
        if(dep[d.get(i)]%2==0)ask[i]=color;
        else{
            if(d.get(i)>=l&&d.get(i)<=r){
                ask[i]=-1;
            }
            else{
                ask[i]=n;
            }
        }
    }
    // for(int x:ask)cout<<x<<" ";
    // cout<<"\n";
    dd.init(n);
    for(int i=0;i<n;i++){
        for(auto to:g[i]){
            if(ask[i]==ask[to])dd.unite(i,to);
        }
    }
    vector<int> vec;
    for(int i=0;i<n;i++)vec.pb(dd.get(i));
    sort(all(vec));
    vec.erase(unique(all(vec)),vec.end());
    // cout<<perform_experiment(ask)<<" "<<sz(vec)<<"\n";
    return (perform_experiment(ask)!=sz(vec));
}

vector<int> find_colours(int N,vector<int> X,vector<int> Y){
    n=N;
    for(int i=0;i<sz(X);i++){
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);
    }
    d.init(n);
    for(int i=1;i<N;i++){
        vector<int> v;
        for(auto to:g[i]){
            if(to<i){
                v.pb(d.get(to));
            }
        }
        sort(all(v));
        v.erase(unique(all(v)),v.end());
        int l=0;
        vector<int> mrg;
        while(l<sz(v)&&bar(i,v[l],v.back())){
            int r=sz(v)-2,res=sz(v)-1;
            int L=l;
            while(L<=r){
                int mid=(L+r)/2;
                if(bar(i,v[l],v[mid])){
                    r=mid-1;
                    res=mid;
                }
                else{
                    L=mid+1;
                }
            }
            l=res+1;
            mrg.pb(v[res]);
        }
        for(auto to:mrg){
            d.unite(i,to);
        }
    }
    vector<int> cmp;
    for(int i=0;i<n;i++)cmp.pb(d.get(i));
    sort(all(cmp));
    cmp.erase(unique(all(cmp)),cmp.end());
    for(int i=0;i<n;i++){
        for(auto to:g[i]){
            if(d.get(i)!=d.get(to)){
                g1[d.get(i)].pb(d.get(to));
                g1[d.get(to)].pb(d.get(i));
            }
        }
    }
    for(int i=0;i<n;i++){
        sort(all(g1[i]));
        g1[i].erase(unique(all(g1[i])),g1[i].end());
    }
    vector<int> ans(n,-1);
    dfs(cmp[0]);
    if(ver[0].empty()||ver[1].empty()){
        if(ver[0].empty())swap(ver[0],ver[1]);
        for(int i=0;i<n;i++){
            vector<int> ask(n,-1);
            ask[0]=i;
            // cout<<perform_experiment(ask)<<"\n";
            if(perform_experiment(ask)==1)return vector<int>(n,i);
        }
    }
    for(int i=0;i<n;i++){
        int l=0;
        vector<int> vertex;
        while(l<sz(ver[1])&&BAR(ver[1][l],ver[1][sz(ver[1])-1],i)){
            int r=sz(ver[1])-2,res=sz(ver[1])-1;
            int L=l;
            while(L<=r){
                int mid=(L+r)/2;
                if(BAR(ver[1][l],ver[1][mid],i)){
                    r=mid-1;
                    res=mid;
                }
                else L=mid+1;
            }
            vertex.pb(ver[1][res]);
            l=res+1;
        }
        for(auto v:vertex){
            for(int j=0;j<n;j++){
                if(d.get(j)==v)ans[j]=i;
            }
        }
    }
    swap(ver[0],ver[1]);
    for(int i=0;i<n;i++)dep[i]^=1;
    for(int i=0;i<n;i++){
        int l=0;
        vector<int> vertex;
        // if(i==0)cout<<BAR(ver[1][l],ver[1][sz(ver[1])-1],i)<<"\n";
        while(l<sz(ver[1])&&BAR(ver[1][l],ver[1][sz(ver[1])-1],i)){
            int r=sz(ver[1])-2,res=sz(ver[1])-1;
            int L=l;
            while(L<=r){
                int mid=(L+r)/2;
                if(BAR(ver[1][l],ver[1][mid],i)){
                    r=mid-1;
                    res=mid;
                }
                else L=mid+1;
            }
            vertex.pb(ver[1][res]);
            l=res+1;
        }
        for(auto v:vertex){
            for(int j=0;j<n;j++){
                if(d.get(j)==v)ans[j]=i;
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 14

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 5
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 0 ms 336 KB #experiments: 3

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 14
2 Correct 1 ms 336 KB #experiments: 2
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 5
5 Correct 0 ms 336 KB #experiments: 3
6 Correct 2 ms 336 KB #experiments: 74
7 Correct 4 ms 336 KB #experiments: 149
8 Correct 4 ms 336 KB #experiments: 159
9 Correct 4 ms 336 KB #experiments: 164
10 Correct 4 ms 336 KB #experiments: 181
11 Correct 5 ms 336 KB #experiments: 208
12 Correct 9 ms 336 KB #experiments: 419
13 Correct 10 ms 336 KB #experiments: 433
14 Correct 4 ms 336 KB #experiments: 64
15 Incorrect 16 ms 496 KB Invalid value of G[2]: -1
16 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 5
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 0 ms 336 KB #experiments: 3
5 Correct 2 ms 336 KB #experiments: 74
6 Correct 4 ms 336 KB #experiments: 149
7 Correct 4 ms 336 KB #experiments: 159
8 Correct 4 ms 336 KB #experiments: 164
9 Correct 4 ms 336 KB #experiments: 181
10 Correct 5 ms 336 KB #experiments: 208
11 Correct 9 ms 336 KB #experiments: 419
12 Correct 10 ms 336 KB #experiments: 433
13 Correct 28 ms 336 KB #experiments: 749
14 Correct 29 ms 476 KB #experiments: 755
15 Correct 26 ms 336 KB #experiments: 781
16 Correct 30 ms 336 KB #experiments: 806
17 Correct 44 ms 468 KB #experiments: 1025
18 Correct 56 ms 476 KB #experiments: 1413
19 Correct 83 ms 476 KB #experiments: 2258
20 Correct 13 ms 336 KB #experiments: 383
21 Correct 106 ms 472 KB #experiments: 2741

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 5
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 0 ms 336 KB #experiments: 3
5 Correct 4 ms 336 KB #experiments: 64
6 Incorrect 16 ms 496 KB Invalid value of G[2]: -1
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 14
2 Correct 1 ms 336 KB #experiments: 2
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 5
5 Correct 0 ms 336 KB #experiments: 3
6 Correct 2 ms 336 KB #experiments: 74
7 Correct 4 ms 336 KB #experiments: 149
8 Correct 4 ms 336 KB #experiments: 159
9 Correct 4 ms 336 KB #experiments: 164
10 Correct 4 ms 336 KB #experiments: 181
11 Correct 5 ms 336 KB #experiments: 208
12 Correct 9 ms 336 KB #experiments: 419
13 Correct 10 ms 336 KB #experiments: 433
14 Correct 4 ms 336 KB #experiments: 64
15 Incorrect 16 ms 496 KB Invalid value of G[2]: -1
16 Halted 0 ms 0 KB -