| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 624086 |
2022-08-07T08:26:04 Z |
radal |
Library (JOI18_library) |
C++17 |
|
287 ms |
328 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
208 KB |
# of queries: 2676 |
| 2 |
Correct |
22 ms |
208 KB |
# of queries: 2722 |
| 3 |
Correct |
40 ms |
292 KB |
# of queries: 2832 |
| 4 |
Correct |
29 ms |
208 KB |
# of queries: 2918 |
| 5 |
Correct |
35 ms |
284 KB |
# of queries: 2902 |
| 6 |
Correct |
31 ms |
292 KB |
# of queries: 2868 |
| 7 |
Correct |
40 ms |
300 KB |
# of queries: 2904 |
| 8 |
Correct |
33 ms |
288 KB |
# of queries: 2760 |
| 9 |
Correct |
38 ms |
208 KB |
# of queries: 2892 |
| 10 |
Correct |
23 ms |
288 KB |
# of queries: 1656 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
208 KB |
# of queries: 6 |
| 13 |
Correct |
1 ms |
208 KB |
# of queries: 16 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 16 |
| 15 |
Correct |
2 ms |
208 KB |
# of queries: 104 |
| 16 |
Correct |
4 ms |
208 KB |
# of queries: 254 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
208 KB |
# of queries: 2676 |
| 2 |
Correct |
22 ms |
208 KB |
# of queries: 2722 |
| 3 |
Correct |
40 ms |
292 KB |
# of queries: 2832 |
| 4 |
Correct |
29 ms |
208 KB |
# of queries: 2918 |
| 5 |
Correct |
35 ms |
284 KB |
# of queries: 2902 |
| 6 |
Correct |
31 ms |
292 KB |
# of queries: 2868 |
| 7 |
Correct |
40 ms |
300 KB |
# of queries: 2904 |
| 8 |
Correct |
33 ms |
288 KB |
# of queries: 2760 |
| 9 |
Correct |
38 ms |
208 KB |
# of queries: 2892 |
| 10 |
Correct |
23 ms |
288 KB |
# of queries: 1656 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
208 KB |
# of queries: 6 |
| 13 |
Correct |
1 ms |
208 KB |
# of queries: 16 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 16 |
| 15 |
Correct |
2 ms |
208 KB |
# of queries: 104 |
| 16 |
Correct |
4 ms |
208 KB |
# of queries: 254 |
| 17 |
Correct |
287 ms |
292 KB |
# of queries: 18846 |
| 18 |
Correct |
261 ms |
288 KB |
# of queries: 18592 |
| 19 |
Correct |
285 ms |
292 KB |
# of queries: 18602 |
| 20 |
Correct |
256 ms |
292 KB |
# of queries: 17502 |
| 21 |
Correct |
225 ms |
296 KB |
# of queries: 16572 |
| 22 |
Correct |
263 ms |
292 KB |
# of queries: 18776 |
| 23 |
Correct |
276 ms |
292 KB |
# of queries: 18744 |
| 24 |
Correct |
120 ms |
292 KB |
# of queries: 8656 |
| 25 |
Correct |
265 ms |
304 KB |
# of queries: 18394 |
| 26 |
Correct |
201 ms |
288 KB |
# of queries: 17100 |
| 27 |
Correct |
105 ms |
292 KB |
# of queries: 8576 |
| 28 |
Correct |
252 ms |
296 KB |
# of queries: 18986 |
| 29 |
Correct |
271 ms |
328 KB |
# of queries: 18964 |
| 30 |
Correct |
233 ms |
292 KB |
# of queries: 18986 |
