oj.uz

Submission #1099949

# Submission time Handle Problem Language Result Execution time Memory
1099949 2024-10-12T08:04:31 Z ttamx Sphinx's Riddle (IOI24_sphinx) C++17
100 / 100
 1030 ms 2640 KB 
#include <bits/stdc++.h>
#include "sphinx.h"

using namespace std;

vector<int> find_colours(int n,vector<int> X,vector<int> Y){
    int m=X.size();
    vector<int> ans(n,-1);
    auto count_col=[&](vector<int> a,int col){
        vector<int> pa(n);
        iota(pa.begin(),pa.end(),0);
        function<int(int)> fp=[&](int u){
            return pa[u]=(u==pa[u]?u:fp(pa[u]));
        };
        auto uni=[&](int u,int v){
            u=fp(u),v=fp(v);
            if(u!=v){
                pa[v]=u;
            }
        };
        for(int i=0;i<m;i++){
            if(a[X[i]]==col&&a[Y[i]]==col){
                uni(X[i],Y[i]);
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            if(a[i]==col&&fp(i)==i){
                res++;
            }
        }
        return res;
    };
    auto query=[&](vector<int> a,int col){
        int res=perform_experiment(a)-count_col(a,col);
        if(col!=n){
            res-=count_col(a,n);
        }
        return res;
    };
    int comp_cnt=0;
    vector<int> pa(n);
    iota(pa.begin(),pa.end(),0);
    function<int(int)> fp=[&](int u){
        return pa[u]=(u==pa[u]?u:fp(pa[u]));
    };
    auto uni=[&](int u,int v){
        u=fp(u),v=fp(v);
        if(u!=v){
            pa[v]=u;
            comp_cnt--;
        }
    };
    vector<int> filter(n,n);
    for(int u=0;u<n;u++){
        comp_cnt++;
        filter[u]=-1;
        int res=query(filter,n);
        int k=comp_cnt-res;
        vector<int> same,cand;
        for(int i=0;i<u;i++){
            if(fp(i)==i){
                cand.emplace_back(i);
            }
        }
        for(int i=0,p=0;i<k;i++){
            int l=p,r=cand.size()-1;
            while(l<r){
                int m=(l+r)/2;
                vector<int> tmp(n,n);
                int cnt=0;
                for(int j=0;j<u;j++){
                    if(cand[p]<=fp(j)&&fp(j)<=cand[m]){
                        if(fp(j)==j){
                            cnt++;
                        }
                    }else{
                        tmp[j]=-1;
                    }
                }
                tmp[u]=-1;
                if(query(tmp,n)!=res-cnt){
                    r=m;
                }else{
                    l=m+1;
                }
            }
            same.emplace_back(cand[l]);
            p=l+1;
        }
        for(auto x:same){
            uni(u,x);
        }
    }
    set<pair<int,int>> edge;
    for(int i=0;i<m;i++){
        int u=fp(X[i]),v=fp(Y[i]);
        if(u>v){
            swap(u,v);
        }
        if(u!=v){
            edge.emplace(u,v);
        }
    }
    vector<vector<int>> adj(n);
    for(auto [u,v]:edge){
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector<vector<int>> comp(n);
    for(int i=0;i<n;i++){
        comp[fp(i)].emplace_back(i);
    }
    vector<bool> vis(n);
    vector<vector<int>> node(2);
    int node_cnt=0;
    function<void(int,int)> dfs=[&](int u,int c){
        node_cnt++;
        vis[u]=true;
        node[c].emplace_back(u);
        for(auto v:adj[u]){
            if(!vis[v]){
                dfs(v,c^1);
            }
        }
    };
    for(auto &x:node){
        sort(x.begin(),x.end());
    }
    dfs(fp(0),0);
    auto paint=[&](vector<int> &a,int i,int col){
        for(auto x:comp[i]){
            a[x]=col;
        }
    };
    if(node_cnt==1){
        for(int i=0;i<n;i++){
            vector<int> tmp(n,i);
            tmp[0]=-1;
            if(perform_experiment(tmp)==1){
                return vector<int>(n,i);
            }
        }
        assert(false);
    }
    vector<vector<int>> pos(2);
    for(int i=0;i<2;i++){
        int k=node[i].size();
        pos[i].resize(k);
        iota(pos[i].begin(),pos[i].end(),0);
    }
    for(int col=0;col<n;col++){
        for(int t=0;t<2;t++){
            vector<int> filter(n,col);
            for(auto i:node[t]){
                paint(filter,i,-1);
            }
            vector<int> found;
            for(int i=0;i<pos[t].size();i++){
                for(int j=0;j<pos[t][i];j++){
                    paint(filter,node[t][j],n);
                }
                if(query(filter,col)==node[t].size()-pos[t][i]){
                    break;
                }
                int l=i,r=pos[t].size()-1;
                while(l<r){
                    int m=(l+r)/2;
                    vector<int> tmp(n,col);
                    for(int j=0;j<node[t].size();j++){
                        if(j<pos[t][i]||pos[t][m]<j){
                            paint(tmp,node[t][j],n);
                        }else{
                            paint(tmp,node[t][j],-1);
                        }
                    }
                    if(query(tmp,col)!=pos[t][m]-pos[t][i]+1){
                        r=m;
                    }else{
                        l=m+1;
                    }
                }
                ans[node[t][pos[t][l]]]=col;
                found.emplace_back(pos[t][l]);
                i=l;
            }
            for(auto i:found){
                pos[t].erase(lower_bound(pos[t].begin(),pos[t].end(),i));
            }
        }
    }
    for(int i=0;i<n;i++){
        ans[i]=ans[fp(i)];
        assert(ans[i]!=-1);
    }
    return ans;
}

Compilation message

sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |             for(int i=0;i<pos[t].size();i++){
      |                         ~^~~~~~~~~~~~~~
sphinx.cpp:163:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |                 if(query(filter,col)==node[t].size()-pos[t][i]){
sphinx.cpp:170:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |                     for(int j=0;j<node[t].size();j++){
      |                                 ~^~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 11

Subtask #1
3.0 / 3.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 11
2 Correct 1 ms 344 KB #experiments: 3
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 0 ms 344 KB #experiments: 4
6 Correct 1 ms 344 KB #experiments: 75
7 Correct 2 ms 344 KB #experiments: 142
8 Correct 3 ms 344 KB #experiments: 225
9 Correct 2 ms 344 KB #experiments: 192
10 Correct 3 ms 440 KB #experiments: 253
11 Correct 3 ms 344 KB #experiments: 274
12 Correct 5 ms 344 KB #experiments: 353
13 Correct 4 ms 344 KB #experiments: 355
14 Correct 1 ms 344 KB #experiments: 65
15 Correct 4 ms 452 KB #experiments: 204
16 Correct 5 ms 344 KB #experiments: 250
17 Correct 6 ms 344 KB #experiments: 285
18 Correct 7 ms 452 KB #experiments: 325
19 Correct 7 ms 344 KB #experiments: 324
20 Correct 10 ms 456 KB #experiments: 353
21 Correct 10 ms 344 KB #experiments: 360
22 Correct 5 ms 344 KB #experiments: 252
23 Correct 4 ms 344 KB #experiments: 253
24 Correct 3 ms 344 KB #experiments: 260
25 Correct 4 ms 344 KB #experiments: 297
26 Correct 4 ms 432 KB #experiments: 311
27 Correct 4 ms 344 KB #experiments: 334
28 Correct 3 ms 344 KB #experiments: 357
29 Correct 4 ms 440 KB #experiments: 297
30 Correct 4 ms 344 KB #experiments: 341
31 Correct 5 ms 456 KB #experiments: 288
32 Correct 7 ms 344 KB #experiments: 344
33 Correct 2 ms 344 KB #experiments: 118
34 Correct 6 ms 344 KB #experiments: 370

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 3
2 Correct 0 ms 344 KB #experiments: 5
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 4
5 Correct 1 ms 344 KB #experiments: 75
6 Correct 2 ms 344 KB #experiments: 142
7 Correct 3 ms 344 KB #experiments: 225
8 Correct 2 ms 344 KB #experiments: 192
9 Correct 3 ms 440 KB #experiments: 253
10 Correct 3 ms 344 KB #experiments: 274
11 Correct 5 ms 344 KB #experiments: 353
12 Correct 4 ms 344 KB #experiments: 355
13 Correct 11 ms 344 KB #experiments: 471
14 Correct 20 ms 600 KB #experiments: 867
15 Correct 28 ms 444 KB #experiments: 1222
16 Correct 37 ms 340 KB #experiments: 1174
17 Correct 41 ms 420 KB #experiments: 1677
18 Correct 53 ms 428 KB #experiments: 1986
19 Correct 51 ms 600 KB #experiments: 2273
20 Correct 8 ms 344 KB #experiments: 384
21 Correct 50 ms 344 KB #experiments: 2388

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 3
2 Correct 0 ms 344 KB #experiments: 5
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 4
5 Correct 1 ms 344 KB #experiments: 65
6 Correct 4 ms 452 KB #experiments: 204
7 Correct 5 ms 344 KB #experiments: 250
8 Correct 6 ms 344 KB #experiments: 285
9 Correct 7 ms 452 KB #experiments: 325
10 Correct 7 ms 344 KB #experiments: 324
11 Correct 10 ms 456 KB #experiments: 353
12 Correct 10 ms 344 KB #experiments: 360
13 Correct 241 ms 904 KB #experiments: 821
14 Correct 457 ms 908 KB #experiments: 1349
15 Correct 534 ms 912 KB #experiments: 1630
16 Correct 611 ms 856 KB #experiments: 1912
17 Correct 660 ms 912 KB #experiments: 2169
18 Correct 705 ms 1104 KB #experiments: 2234
19 Correct 698 ms 1680 KB #experiments: 2329
20 Correct 75 ms 856 KB #experiments: 310
21 Correct 691 ms 2640 KB #experiments: 2393

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 11
2 Correct 1 ms 344 KB #experiments: 3
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 0 ms 344 KB #experiments: 4
6 Correct 1 ms 344 KB #experiments: 75
7 Correct 2 ms 344 KB #experiments: 142
8 Correct 3 ms 344 KB #experiments: 225
9 Correct 2 ms 344 KB #experiments: 192
10 Correct 3 ms 440 KB #experiments: 253
11 Correct 3 ms 344 KB #experiments: 274
12 Correct 5 ms 344 KB #experiments: 353
13 Correct 4 ms 344 KB #experiments: 355
14 Correct 1 ms 344 KB #experiments: 65
15 Correct 4 ms 452 KB #experiments: 204
16 Correct 5 ms 344 KB #experiments: 250
17 Correct 6 ms 344 KB #experiments: 285
18 Correct 7 ms 452 KB #experiments: 325
19 Correct 7 ms 344 KB #experiments: 324
20 Correct 10 ms 456 KB #experiments: 353
21 Correct 10 ms 344 KB #experiments: 360
22 Correct 5 ms 344 KB #experiments: 252
23 Correct 4 ms 344 KB #experiments: 253
24 Correct 3 ms 344 KB #experiments: 260
25 Correct 4 ms 344 KB #experiments: 297
26 Correct 4 ms 432 KB #experiments: 311
27 Correct 4 ms 344 KB #experiments: 334
28 Correct 3 ms 344 KB #experiments: 357
29 Correct 4 ms 440 KB #experiments: 297
30 Correct 4 ms 344 KB #experiments: 341
31 Correct 5 ms 456 KB #experiments: 288
32 Correct 7 ms 344 KB #experiments: 344
33 Correct 2 ms 344 KB #experiments: 118
34 Correct 6 ms 344 KB #experiments: 370
35 Correct 11 ms 344 KB #experiments: 471
36 Correct 20 ms 600 KB #experiments: 867
37 Correct 28 ms 444 KB #experiments: 1222
38 Correct 37 ms 340 KB #experiments: 1174
39 Correct 41 ms 420 KB #experiments: 1677
40 Correct 53 ms 428 KB #experiments: 1986
41 Correct 51 ms 600 KB #experiments: 2273
42 Correct 8 ms 344 KB #experiments: 384
43 Correct 50 ms 344 KB #experiments: 2388
44 Correct 241 ms 904 KB #experiments: 821
45 Correct 457 ms 908 KB #experiments: 1349
46 Correct 534 ms 912 KB #experiments: 1630
47 Correct 611 ms 856 KB #experiments: 1912
48 Correct 660 ms 912 KB #experiments: 2169
49 Correct 705 ms 1104 KB #experiments: 2234
50 Correct 698 ms 1680 KB #experiments: 2329
51 Correct 75 ms 856 KB #experiments: 310
52 Correct 691 ms 2640 KB #experiments: 2393
53 Correct 102 ms 460 KB #experiments: 2224
54 Correct 128 ms 472 KB #experiments: 2121
55 Correct 135 ms 600 KB #experiments: 2183
56 Correct 142 ms 480 KB #experiments: 2094
57 Correct 366 ms 1360 KB #experiments: 1747
58 Correct 323 ms 1120 KB #experiments: 1853
59 Correct 291 ms 1104 KB #experiments: 1712
60 Correct 351 ms 1144 KB #experiments: 2097
61 Correct 61 ms 344 KB #experiments: 2254
62 Correct 47 ms 344 KB #experiments: 2253
63 Correct 48 ms 448 KB #experiments: 2348
64 Correct 108 ms 592 KB #experiments: 1982
65 Correct 103 ms 344 KB #experiments: 2076
66 Correct 140 ms 480 KB #experiments: 2087
67 Correct 131 ms 344 KB #experiments: 2129
68 Correct 123 ms 476 KB #experiments: 2023
69 Correct 123 ms 488 KB #experiments: 2101
70 Correct 133 ms 468 KB #experiments: 2105
71 Correct 119 ms 344 KB #experiments: 1970
72 Correct 84 ms 452 KB #experiments: 2210
73 Correct 111 ms 592 KB #experiments: 2096
74 Correct 141 ms 592 KB #experiments: 2179
75 Correct 116 ms 344 KB #experiments: 1985
76 Correct 130 ms 592 KB #experiments: 2088
77 Correct 120 ms 472 KB #experiments: 1946
78 Correct 149 ms 476 KB #experiments: 1969
79 Correct 141 ms 344 KB #experiments: 1892
80 Correct 145 ms 344 KB #experiments: 1995
81 Correct 142 ms 480 KB #experiments: 2081
82 Correct 221 ms 760 KB #experiments: 2343
83 Correct 589 ms 600 KB #experiments: 1788
84 Correct 1030 ms 1672 KB #experiments: 2307
85 Correct 31 ms 552 KB #experiments: 472
86 Correct 366 ms 1096 KB #experiments: 2389