| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1170625 | browntoad | Mouse (info1cup19_mouse) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
// #define TOAD
#ifdef TOAD
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
const ll maxn = 1e5+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;
#ifdef TOAD
int query(vector<int> pus){
for (auto x:pus) cout<<x<<' ';
cout<<endl<<flush;
int in; cin>>in;
return in;
}
#endif
void solve(int N){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> otot(N); // out
REP(i, N) otot[i] = i+1; // ONE_BASE!!
if (N <= 2){
if (N == 1){
query(otot);
return;
}
int ret = query(otot);
if (ret == 0){
swap(otot[0], otot[1]);
query(otot);
}
return;
}
vector<int> rem = otot;
fill(ALL(otot), -1);
vector<int> ids = vector<int> (N);
REP(i, N) ids[i] = i; // ZERO BASE!
int okid = -1, plea = 0;
while(1){
shuffle(ALL(rem), rng);
REP(j, SZ(rem)){
otot[ids[j]] = rem[j];
}
vector<int> blacklist(N);
int ret = query(otot), tret;
if (ret == N) return;
if (ret == plea) continue; // no new
if (SZ(rem) < N){ // just match with the okid
REP(j, SZ(rem)){
swap(otot[ids[j]], otot[okid]);
tret = query(otot); if (tret == N) return;
swap(otot[ids[j]], otot[okid]);
if (tret - ret == -2){
blacklist[j] = 1;
}
}
}
else{
swap(otot[0], otot[1]);
tret = query(otot); if (tret == N) return;
swap(otot[0], otot[1]);
if (tret - ret == -2){ // both are 1s
blacklist[0] = blacklist[1] = 1;
okid = 0;
FOR(j, 2, N){
swap(otot[ids[j]], otot[okid]);
tret = query(otot); if (tret == N) return;
swap(otot[ids[j]], otot[okid]);
if (tret - ret == -2){
blacklist[j] = 1;
}
}
}
else if (tret - ret >= 0){ // both are fails
FOR(j, 2, N){
swap(otot[0], otot[j]);
tret = query(otot); if (tret == N) return;
swap(otot[0], otot[j]);
if (tret - ret == -1){
okid = j;
blacklist[j] = 1;
}
}
}
else{
swap(otot[1], otot[2]);
tret = query(otot); if (tret == N) return;
swap(otot[1], otot[2]);
if (tret - ret == -1){ // either 101 or 010
swap(otot[0], otot[2]);
tret = query(otot); if (tret == N) return;
swap(otot[0], otot[2]);
if (tret - ret == -2){
okid = 0;
blacklist[0] = blacklist[2] = 1;
}
else{
okid = 1;
blacklist[1] = 1;
}
}
else if (tret - ret == -2){
okid = 1;
blacklist[1] = blacklist[2] = 1;
}
else{
okid = 0;
blacklist[0] = 1;
}
FOR(j, 3, N){
swap(otot[ids[j]], otot[okid]);
tret = query(otot); if (tret == N) return;
swap(otot[ids[j]], otot[okid]);
if (tret - ret == -2){
blacklist[j] = 1;
}
}
}
}
vector<int> trem, tid;
REP(j, SZ(rem)){
if (!blacklist[j]) {
trem.pb(rem[j]);
tid.pb(ids[j]);
}
else{
plea++;
otot[ids[j]] = rem[j];
}
}
rem = trem;
ids = tid;
}
}
#ifdef TOAD
signed main(){
IOS();
int n; cin>>n;
//cout<<n/0.63 * n/2<<endl;
solve(n);
}
#endif