Submission #574997

#TimeUsernameProblemLanguageResultExecution timeMemory
574997Valters07Finding Routers (IOI20_routers)C++14
98.13 / 100
4 ms596 KiB
#include <bits/stdc++.h> #include "routers.h" #pragma GCC optimize("O2,unroll-loops") #define fio ios_base::sync_with_stdio(0);cin.tie(0); #define ll long long #define en cin.close();return 0; #define pb push_back #define fi first//printf("%lli\n",cur); #define se second//scanf("%lli",&n); #define r0 return 0; using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<int> find_routers(int len, int n, int q) { vector<int> ans(n); int idx = 0, lst = 0, sq = sqrt(n); map<int,int> mp; for(int i = 1;i<n;i++) { int l = lst+1, r = len; if(n!=2){ while(l+sq<r) { int pos = l+sq, ind = (mp.count(pos)?mp[pos]:use_detector(pos)); mp[pos]=ind; if(ind==idx) l=pos; else { r=pos; break; } } } while(l<r) { int mid = (l+r+1)/2, ind = (mp.count(mid)?mp[mid]:use_detector(mid)); mp[mid]=ind; if(ind==idx) l=mid; else r=mid-1; } int nwpos = lst + (l-lst)*2, nwind = (mp.count(nwpos)?mp[nwpos]:use_detector(nwpos)); mp[nwpos]=nwind; ans[nwind]=nwpos; lst=nwpos; idx=nwind; } 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...