Submission #624086

#TimeUsernameProblemLanguageResultExecution timeMemory
624086radalLibrary (JOI18_library)C++17
100 / 100
287 ms328 KiB
#include <bits/stdc++.h> #include "library.h" #pragma GCC target("sse,sse2,avx2") #pragma GCC optimize("unroll-loops,O2") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pll; constexpr int N = 1e3+10,mod = 998244353,inf = 1e9+10; int moj[N][2]; void Solve(int n){ if (n == 1){ vector<int> ve; ve.pb(1); Answer(ve); return; } memset(moj,-1,sizeof moj); vector<int> ask; ask.resize(n); rep(i,1,n+1){ if (moj[i][0] != -1 && moj[i][1] != -1) continue; if (moj[i][0] != -1){ int v = moj[i][0]; rep(j,0,v){ if (j == i-1) continue; ask[j] = 1; } rep(j,v,n) ask[j] = 0; int x = Query(ask); ask[i-1] = 1; int y = Query(ask); if (y-x == -1){ int l = i,r = v-1,m; while (r-l > 1){ m = (l+r) >> 1; ask[i-1] = 0; rep(j,0,m){ if (j == i-1) continue; ask[j] = 1; } rep(j,m,n) ask[j] = 0; x = Query(ask); ask[i-1] = 1; y = Query(ask); if (y-x > 0) l = m; else r = m; } moj[i][1] = r; if (moj[r][0] == -1) moj[r][0] = i; else moj[r][1] = i; continue; } int l = v,r = n+1,m; while (r-l > 1){ m = (l+r) >> 1; ask[i-1] = 0; rep(j,0,m){ if (j == i-1) continue; ask[j] = 1; } rep(j,m,n) ask[j] = 0; x = Query(ask); ask[i-1] = 1; y = Query(ask); if (y-x == 0) l = m; else r = m; } if (r == n+1) continue; moj[i][1] = r; if (moj[r][0] == -1) moj[r][0] = i; else moj[r][1] = i; continue; } int l = i,r = n+1,m,r2 = n+1,x,y; while (r-l > 1){ m = (l+r) >> 1; ask[i-1] = 0; rep(j,0,m){ if (j == i-1) continue; ask[j] = 1; } rep(j,m,n) ask[j] = 0; x = Query(ask); ask[i-1] = 1; y = Query(ask); if (y-x == 1) l = m; else{ r = m; if (y-x == -1) r2 = m; } } moj[i][0] = r; if (moj[r][0] == -1) moj[r][0] = i; else moj[r][1] = i; l = r; r = r2; while (r-l > 1){ m = (l+r) >> 1; ask[i-1] = 0; rep(j,0,m){ if (j == i-1) continue; ask[j] = 1; } rep(j,m,n) ask[j] = 0; x = Query(ask); ask[i-1] = 1; y = Query(ask); if (y-x == 0) l = m; else r = m; } if (r == n+1) continue; moj[i][1] = r; if (moj[r][0] == -1) moj[r][0] = i; else moj[r][1] = i; } vector<int> ans; int cur = 1,perv = -1; rep(i,1,n+1) if (moj[i][1] == -1) cur = i; while (cur > 0){ ans.pb(cur); if (ans.size() == n) break; if (moj[cur][0] == perv){ perv = cur; cur = moj[cur][1]; } else{ perv = cur; cur = moj[cur][0]; } } Answer(ans); }

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:131:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  131 |         if (ans.size() == n) break;
      |             ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...