Submission #1201242

#TimeUsernameProblemLanguageResultExecution timeMemory
1201242ansoriSphinx's Riddle (IOI24_sphinx)C++20
10 / 100
32 ms1176 KiB
#include "sphinx.h" #include<bits/stdc++.h> #define ll long long using namespace std; const int msz = 256; int perform_experiment(vector<int> E); //47.5 points int n , m; vector<int> G , g[msz] , col; vector<bool> w; void dfs(int v){ w[v] = 1; for(auto to : g[v]){ if((! w[to]) and col[to] == col[v]){ dfs(to); } } } int expected(){ w = vector<bool> (n , 0); int cmp = 0; for(int i = 0;i < n; ++ i){ if(! w[i]){ cmp ++; dfs(i); } } return cmp; } vector<int> find_colours(int N, std::vector<int> x, std::vector<int> y) { n = N , m = x.size(); G = vector<int> (n , 0); bool ok = true; for(int i = 0;i < m; ++ i){ g[x[i]].push_back(y[i]); g[y[i]].push_back(x[i]); if(x[i] != i or y[i] != i + 1) ok = false; } if(n <= 52){ col = vector<int> (n , n); for(int i = 0;i < n; ++ i){ col[i] = -1; col[g[i][0]] = -1; int cmp = expected(); for(int j = 0;j < n; ++ j){ vector<int> qu(n , n); qu[i] = -1; qu[g[i][0]] = j; if(perform_experiment(qu) == cmp){ G[i] = j; break; } } col[i] = n; col[g[i][0]] = n; } return G; } if(m == (n * (n - 1)) / 2){ for(int i = 0;i < n; ++ i){ int l = 0; int r = n; while(l + 1 < r){ int mid = (l + r) / 2; vector<int> qu(n , n); for(int j = 0;j < (r - mid); ++ j){ qu[g[i][j]] = mid + j; } if(perform_experiment(qu) == (r - mid + 1)) l = mid; else r = mid; } G[i] = l; } return G; } if(ok){ int c = 0; for(int i = 0;i < n; ++ i){ G[i] = c; for(int j = i + 1;j < n; ++ j){ vector<int> qu(n , n); for(int z = i;z <= j; ++ z) qu[z] = -1; if(perform_experiment(qu) == 1 + (i != 0) + (j != (n - 1))){ i = j; G[j] = c; } else break; } cout << i << '\n'; c ++; } return G; } return G; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...