oj.uz

Submission #1111066

# Submission time Handle Problem Language Result Execution time Memory
1111066 2024-11-11T11:54:04 Z Pioneer Sphinx's Riddle (IOI24_sphinx) C++17
100 / 100
 1114 ms 2004 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;
            }
        }
    }
    // cout<<l<<" "<<r<<"\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]);
    sort(all(ver[0]));
    sort(all(ver[1]));
    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;
    // cout<<d.get(0)<<"\n";
    // for(int x:ver[1])cout<<x<<" ";
    // cout<<"\n";
    for(int i=0;i<n;i++){
        int l=0;
        vector<int> vertex;
        // if(i==17){
        //     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 512 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 5
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 3

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 14
2 Correct 1 ms 512 KB #experiments: 2
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 5
5 Correct 1 ms 336 KB #experiments: 3
6 Correct 3 ms 336 KB #experiments: 74
7 Correct 4 ms 336 KB #experiments: 149
8 Correct 5 ms 336 KB #experiments: 159
9 Correct 5 ms 336 KB #experiments: 164
10 Correct 5 ms 336 KB #experiments: 181
11 Correct 5 ms 336 KB #experiments: 208
12 Correct 9 ms 336 KB #experiments: 419
13 Correct 11 ms 336 KB #experiments: 433
14 Correct 3 ms 336 KB #experiments: 64
15 Correct 12 ms 532 KB #experiments: 290
16 Correct 14 ms 620 KB #experiments: 309
17 Correct 11 ms 336 KB #experiments: 336
18 Correct 12 ms 496 KB #experiments: 380
19 Correct 17 ms 336 KB #experiments: 390
20 Correct 15 ms 336 KB #experiments: 414
21 Correct 12 ms 336 KB #experiments: 433
22 Correct 11 ms 336 KB #experiments: 388
23 Correct 11 ms 336 KB #experiments: 381
24 Correct 10 ms 336 KB #experiments: 392
25 Correct 13 ms 336 KB #experiments: 413
26 Correct 7 ms 336 KB #experiments: 300
27 Correct 8 ms 336 KB #experiments: 356
28 Correct 11 ms 504 KB #experiments: 405
29 Correct 9 ms 336 KB #experiments: 306
30 Correct 12 ms 336 KB #experiments: 393
31 Correct 11 ms 336 KB #experiments: 326
32 Correct 16 ms 336 KB #experiments: 392
33 Correct 3 ms 336 KB #experiments: 84
34 Correct 15 ms 592 KB #experiments: 432

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 5
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 3
5 Correct 3 ms 336 KB #experiments: 74
6 Correct 4 ms 336 KB #experiments: 149
7 Correct 5 ms 336 KB #experiments: 159
8 Correct 5 ms 336 KB #experiments: 164
9 Correct 5 ms 336 KB #experiments: 181
10 Correct 5 ms 336 KB #experiments: 208
11 Correct 9 ms 336 KB #experiments: 419
12 Correct 11 ms 336 KB #experiments: 433
13 Correct 34 ms 336 KB #experiments: 749
14 Correct 27 ms 336 KB #experiments: 755
15 Correct 29 ms 508 KB #experiments: 781
16 Correct 39 ms 592 KB #experiments: 806
17 Correct 50 ms 336 KB #experiments: 1025
18 Correct 64 ms 336 KB #experiments: 1413
19 Correct 106 ms 336 KB #experiments: 2258
20 Correct 12 ms 336 KB #experiments: 383
21 Correct 120 ms 480 KB #experiments: 2741

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 5
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 3
5 Correct 3 ms 336 KB #experiments: 64
6 Correct 12 ms 532 KB #experiments: 290
7 Correct 14 ms 620 KB #experiments: 309
8 Correct 11 ms 336 KB #experiments: 336
9 Correct 12 ms 496 KB #experiments: 380
10 Correct 17 ms 336 KB #experiments: 390
11 Correct 15 ms 336 KB #experiments: 414
12 Correct 12 ms 336 KB #experiments: 433
13 Correct 309 ms 1408 KB #experiments: 1108
14 Correct 481 ms 1868 KB #experiments: 1604
15 Correct 539 ms 1908 KB #experiments: 1932
16 Correct 581 ms 2004 KB #experiments: 2162
17 Correct 718 ms 1904 KB #experiments: 2439
18 Correct 724 ms 1860 KB #experiments: 2549
19 Correct 774 ms 1792 KB #experiments: 2645
20 Correct 64 ms 1104 KB #experiments: 309
21 Correct 590 ms 1740 KB #experiments: 2741

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 14
2 Correct 1 ms 512 KB #experiments: 2
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 5
5 Correct 1 ms 336 KB #experiments: 3
6 Correct 3 ms 336 KB #experiments: 74
7 Correct 4 ms 336 KB #experiments: 149
8 Correct 5 ms 336 KB #experiments: 159
9 Correct 5 ms 336 KB #experiments: 164
10 Correct 5 ms 336 KB #experiments: 181
11 Correct 5 ms 336 KB #experiments: 208
12 Correct 9 ms 336 KB #experiments: 419
13 Correct 11 ms 336 KB #experiments: 433
14 Correct 3 ms 336 KB #experiments: 64
15 Correct 12 ms 532 KB #experiments: 290
16 Correct 14 ms 620 KB #experiments: 309
17 Correct 11 ms 336 KB #experiments: 336
18 Correct 12 ms 496 KB #experiments: 380
19 Correct 17 ms 336 KB #experiments: 390
20 Correct 15 ms 336 KB #experiments: 414
21 Correct 12 ms 336 KB #experiments: 433
22 Correct 11 ms 336 KB #experiments: 388
23 Correct 11 ms 336 KB #experiments: 381
24 Correct 10 ms 336 KB #experiments: 392
25 Correct 13 ms 336 KB #experiments: 413
26 Correct 7 ms 336 KB #experiments: 300
27 Correct 8 ms 336 KB #experiments: 356
28 Correct 11 ms 504 KB #experiments: 405
29 Correct 9 ms 336 KB #experiments: 306
30 Correct 12 ms 336 KB #experiments: 393
31 Correct 11 ms 336 KB #experiments: 326
32 Correct 16 ms 336 KB #experiments: 392
33 Correct 3 ms 336 KB #experiments: 84
34 Correct 15 ms 592 KB #experiments: 432
35 Correct 34 ms 336 KB #experiments: 749
36 Correct 27 ms 336 KB #experiments: 755
37 Correct 29 ms 508 KB #experiments: 781
38 Correct 39 ms 592 KB #experiments: 806
39 Correct 50 ms 336 KB #experiments: 1025
40 Correct 64 ms 336 KB #experiments: 1413
41 Correct 106 ms 336 KB #experiments: 2258
42 Correct 12 ms 336 KB #experiments: 383
43 Correct 120 ms 480 KB #experiments: 2741
44 Correct 309 ms 1408 KB #experiments: 1108
45 Correct 481 ms 1868 KB #experiments: 1604
46 Correct 539 ms 1908 KB #experiments: 1932
47 Correct 581 ms 2004 KB #experiments: 2162
48 Correct 718 ms 1904 KB #experiments: 2439
49 Correct 724 ms 1860 KB #experiments: 2549
50 Correct 774 ms 1792 KB #experiments: 2645
51 Correct 64 ms 1104 KB #experiments: 309
52 Correct 590 ms 1740 KB #experiments: 2741
53 Correct 138 ms 508 KB #experiments: 1991
54 Correct 145 ms 548 KB #experiments: 1981
55 Correct 177 ms 560 KB #experiments: 1927
56 Correct 186 ms 572 KB #experiments: 1836
57 Correct 501 ms 1084 KB #experiments: 2456
58 Correct 476 ms 1096 KB #experiments: 2520
59 Correct 444 ms 1044 KB #experiments: 2441
60 Correct 489 ms 1064 KB #experiments: 2687
61 Correct 92 ms 476 KB #experiments: 2030
62 Correct 108 ms 592 KB #experiments: 2396
63 Correct 102 ms 336 KB #experiments: 2585
64 Correct 157 ms 536 KB #experiments: 1798
65 Correct 146 ms 536 KB #experiments: 1799
66 Correct 171 ms 552 KB #experiments: 1917
67 Correct 178 ms 564 KB #experiments: 1978
68 Correct 180 ms 572 KB #experiments: 1810
69 Correct 192 ms 636 KB #experiments: 1884
70 Correct 179 ms 564 KB #experiments: 1967
71 Correct 168 ms 644 KB #experiments: 1771
72 Correct 140 ms 500 KB #experiments: 2101
73 Correct 127 ms 508 KB #experiments: 1847
74 Correct 167 ms 532 KB #experiments: 2045
75 Correct 174 ms 556 KB #experiments: 1758
76 Correct 173 ms 556 KB #experiments: 1911
77 Correct 177 ms 644 KB #experiments: 1797
78 Correct 210 ms 592 KB #experiments: 1919
79 Correct 182 ms 604 KB #experiments: 1798
80 Correct 193 ms 856 KB #experiments: 1883
81 Correct 202 ms 852 KB #experiments: 1898
82 Correct 298 ms 840 KB #experiments: 2613
83 Correct 612 ms 1552 KB #experiments: 2031
84 Correct 1114 ms 1708 KB #experiments: 2618
85 Correct 46 ms 592 KB #experiments: 467
86 Correct 409 ms 1008 KB #experiments: 2739