Submission #1274720

#TimeUsernameProblemLanguageResultExecution timeMemory
1274720nicolo_010Highway Tolls (IOI18_highway)C++20
18 / 100
76 ms4696 KiB
#include <bits/stdc++.h> #include "highway.h" using namespace std; using ll = long long; using pii = pair<int, int>; vector<int> query; vector<int> s; vector<int> u, v; bool diff() { int m = query.size(); for (int i=0; i<m; i++) { query[i] = (s[u[i]] == s[v[i]]); } ll w = ask(query); return (w%2==1); } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { int m = U.size(); u = U, v = V; query.assign(m, 0); s.assign(N, 0); vector<int> grp; int xr=0; for (int b=0; b<17; b++) { for (int i=0; i<N; i++) { s[i] = !!(i&(1<<b)); } if (diff()) { xr |= (1<<b); grp = s; } } int l = 0, r = N-1; int ans = 0; while (l <= r) { int mid = (l+r)/2; for (int i=0; i<N; i++) { s[i] = (grp[i] && l <= i && i <= mid); } if (diff()) { r = mid-1; } else { l = mid+1; ans = mid+1; } } answer(ans, ans^xr); }
#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...