| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 624076 |
2022-08-07T08:07:20 Z |
radal |
Library (JOI18_library) |
C++17 |
|
386 ms |
262144 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 = 0,r = v-1,m;
while (r-l > 1){
m = (l+r) >> 1;
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;
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 = 0,r = n+1,m,r2 = n+1,x,y;
while (r-l > 1){
m = (l+r) >> 1;
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;
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 (moj[cur][0] == perv){
perv = cur;
cur = moj[cur][1];
}
else{
perv = cur;
cur = moj[cur][0];
}
}
Answer(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
386 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
386 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
