oj.uz

Submission #1111060

# Submission time Handle Problem Language Result Execution time Memory
1111060 2024-11-11T11:43:46 Z Pioneer Sphinx's Riddle (IOI24_sphinx) C++17
57 / 100
 687 ms 2132 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(d.get(i)==d.get(to))dd.unite(i,to);
            else{
                if(ask[i]!=-1&&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);
        }
        return vector<int>(n,-2);
    }
    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 x:ver[1])cout<<x<<" ";
    // cout<<"\n";
    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 512 KB #experiments: 5
4 Correct 1 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 512 KB #experiments: 5
5 Correct 1 ms 336 KB #experiments: 3
6 Correct 2 ms 336 KB #experiments: 74
7 Correct 4 ms 336 KB #experiments: 149
8 Correct 5 ms 336 KB #experiments: 159
9 Correct 4 ms 504 KB #experiments: 164
10 Correct 5 ms 336 KB #experiments: 181
11 Correct 5 ms 336 KB #experiments: 208
12 Correct 10 ms 336 KB #experiments: 419
13 Correct 10 ms 336 KB #experiments: 433
14 Correct 3 ms 336 KB #experiments: 64
15 Correct 9 ms 336 KB #experiments: 290
16 Correct 11 ms 752 KB #experiments: 309
17 Correct 13 ms 756 KB #experiments: 336
18 Correct 12 ms 336 KB #experiments: 380
19 Correct 12 ms 336 KB #experiments: 390
20 Correct 13 ms 336 KB #experiments: 414
21 Correct 14 ms 336 KB #experiments: 433
22 Incorrect 12 ms 592 KB Invalid value of G[1]: -1
23 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 512 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 3
5 Correct 2 ms 336 KB #experiments: 74
6 Correct 4 ms 336 KB #experiments: 149
7 Correct 5 ms 336 KB #experiments: 159
8 Correct 4 ms 504 KB #experiments: 164
9 Correct 5 ms 336 KB #experiments: 181
10 Correct 5 ms 336 KB #experiments: 208
11 Correct 10 ms 336 KB #experiments: 419
12 Correct 10 ms 336 KB #experiments: 433
13 Correct 31 ms 336 KB #experiments: 749
14 Correct 29 ms 468 KB #experiments: 755
15 Correct 29 ms 476 KB #experiments: 781
16 Correct 35 ms 476 KB #experiments: 806
17 Correct 44 ms 504 KB #experiments: 1025
18 Correct 52 ms 472 KB #experiments: 1413
19 Correct 87 ms 592 KB #experiments: 2258
20 Correct 18 ms 336 KB #experiments: 383
21 Correct 101 ms 336 KB #experiments: 2741

Subtask #4
21.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 512 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 3
5 Correct 3 ms 336 KB #experiments: 64
6 Correct 9 ms 336 KB #experiments: 290
7 Correct 11 ms 752 KB #experiments: 309
8 Correct 13 ms 756 KB #experiments: 336
9 Correct 12 ms 336 KB #experiments: 380
10 Correct 12 ms 336 KB #experiments: 390
11 Correct 13 ms 336 KB #experiments: 414
12 Correct 14 ms 336 KB #experiments: 433
13 Correct 298 ms 1468 KB #experiments: 1108
14 Correct 399 ms 1728 KB #experiments: 1604
15 Correct 455 ms 1908 KB #experiments: 1932
16 Correct 530 ms 2132 KB #experiments: 2162
17 Correct 677 ms 1976 KB #experiments: 2439
18 Correct 687 ms 1856 KB #experiments: 2549
19 Correct 681 ms 1724 KB #experiments: 2645
20 Correct 70 ms 1208 KB #experiments: 309
21 Correct 627 ms 1744 KB #experiments: 2741

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 512 KB #experiments: 5
5 Correct 1 ms 336 KB #experiments: 3
6 Correct 2 ms 336 KB #experiments: 74
7 Correct 4 ms 336 KB #experiments: 149
8 Correct 5 ms 336 KB #experiments: 159
9 Correct 4 ms 504 KB #experiments: 164
10 Correct 5 ms 336 KB #experiments: 181
11 Correct 5 ms 336 KB #experiments: 208
12 Correct 10 ms 336 KB #experiments: 419
13 Correct 10 ms 336 KB #experiments: 433
14 Correct 3 ms 336 KB #experiments: 64
15 Correct 9 ms 336 KB #experiments: 290
16 Correct 11 ms 752 KB #experiments: 309
17 Correct 13 ms 756 KB #experiments: 336
18 Correct 12 ms 336 KB #experiments: 380
19 Correct 12 ms 336 KB #experiments: 390
20 Correct 13 ms 336 KB #experiments: 414
21 Correct 14 ms 336 KB #experiments: 433
22 Incorrect 12 ms 592 KB Invalid value of G[1]: -1
23 Halted 0 ms 0 KB -