Submission #1226674

#TimeUsernameProblemLanguageResultExecution timeMemory
1226674Theo830Sphinx's Riddle (IOI24_sphinx)C++20
0 / 100
0 ms420 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ll,ii> #define id pair<ll,vector<ll> > #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training #include "sphinx.h" std::vector<int> find_colours(int n, std::vector<int> x, std::vector<int> y){ int m = x.size(); std::vector<int> ans(n, 0); f(i,0,n){ vector<int> e(n,-1); f(j,0,n){ e[j] = i; j++; } int posa = perform_experiment(e); posa /= 2; posa = n/2 - posa; ll go = 0; while(posa--){ vector<ll>posi; f(j,1,n){ if(j >= go){ posi.pb(j); } j++; } ll l = 0,r = posi.size()-1; ll res = posi.size()-1; while(l <= r){ ll mid = (l+r)/2; vector<int> e(n,n); ll w = 0; f(j,posi[0]-1,posi[mid]+1){ if(j % 2 == 0){ e[j] = i; } else{ e[j] = -1; } w++; } w += e[0] == n; w += e.back() == n; int x = perform_experiment(e); if(x < w){ r = mid - 1; res = min(res,mid); } else{ l = mid + 1; } } ans[posi[res]] = i; go = posi[res]+1; } } f(i,0,n){ vector<int> e(n,-1); f(j,1,n){ e[j] = i; j++; } int posa = perform_experiment(e); posa++; posa /= 2; posa = (n+1)/2 - posa; ll go = 0; while(posa--){ vector<ll>posi; f(j,0,n){ if(j >= go){ posi.pb(j); } j++; } ll l = 0,r = posi.size()-1; ll res = posi.size()-1; while(l <= r){ ll mid = (l+r)/2; vector<int> e(n,n); ll w = 0; ll LL = posi[0],rr = posi[mid]; if(LL == rr){ if(LL > 0){ LL--; } else{ rr++; } } f(j,LL,rr+1){ if(j % 2){ e[j] = i; } else{ e[j] = -1; } w++; } w += e[0] == n; w += e.back() == n; int x = perform_experiment(e); if(x < w){ r = mid - 1; res = min(res,mid); } else{ l = mid + 1; } } ans[posi[res]] = i; go = posi[res]+1; } } return ans; }
#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...