Submission #1254692

#TimeUsernameProblemLanguageResultExecution timeMemory
1254692random_nameXylophone (JOI18_xylophone)C++20
0 / 100
0 ms408 KiB
#include "xylophone.h" #include <bits/stdc++.h> static int A[5000]; void solve(int N) { int l = 0, r = N-1; while(true) { int m = (l + r) / 2; // std::cout << l << ' ' << r << '\n'; if(query(l+1, m+1) == N-1){ r = m; } else if(query(m+2, r+1) == N-1){ l = m+1; } else{ break; } } int li = (l+r+1) / 2; int ri = r; // std::cout << "----\n"; while(li != ri){ // std::cout << li << ' ' << ri << '\n'; int m = (li + ri) / 2; if(query(l+1, m+1) == N-1){ ri = m; } else{ li = m+1; } } int Max = li; std::set<int> used; std::vector<int> B(N); B[Max] = N; int temp_max = Max; bool accending = false; for(int i = Max+1; i < N; i++){ used.insert(B[i-1]); int diff = query(i, i+1); if(B[i-1] + diff > N || used.count(B[i-1] + diff)){ B[i] = B[i-1] - diff; continue; } if(B[i-1] - diff < 1 || used.count(B[i-1] - diff)){ B[i] = B[i-1] + diff; continue; } int diff2 = query(i-1, i+1); if(diff2 == abs(B[i-1] - B[i-2]) || diff2 == diff){ if(B[i-1] > B[i-2]){ B[i] = B[i-1] - diff; } else{ B[i] = B[i-1] + diff; } continue; } if(B[i-1] > B[i-2]){ B[i] = B[i-1] + diff; } else{ B[i] = B[i-1] - diff; } } for(int i = Max-1; i >= 0; i--){ used.insert(i+1); int diff = query(i+1, i+2); if(B[i+1] + diff > N || used.count(B[i+1] + diff)){ B[i] = B[i+1] - diff; continue; } if(B[i+1] - diff < 1 || used.count(B[i+1] - diff)){ B[i] = B[i+1] + diff; continue; } int diff2 = query(i+1, i+3); if(diff2 == abs(B[i+1] - B[i+2]) || diff2 == diff){ if(B[i+1] > B[i+2]){ B[i] = B[i+1] - diff; } else{ B[i] = B[i+1] + diff; } continue; } if(B[i+1] > B[i+2]){ B[i] = B[i+1] + diff; } else{ B[i] = B[i+1] - diff; } } for(int i = 0; i < N; i++){ // std::cout << B[i] << ' '; answer(i+1, B[i]); } // std::cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...