제출 #1152334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152334		arkanefury	Mouse (info1cup19_mouse)	C++20	9 / 100	52 ms	424 KiB

mouse

#include <bits/stdc++.h>
#include "grader.h"
#define pb push_back
using namespace std;
#define F first
#define sz size()
#define S second
#define in insert
#define all(v) v.begin(), v.end()
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
const int N = 300+5;
int n,m,k,tt,ans,sum=0,l, r, x, y, cnt, block = 448, res;
int a[N][N], b[N], c[N];
vector<int>q, v, lp;
void solve(int n){
    FOR(i, 1, n, 1)q.pb(i);
    while(1){
        random_shuffle(all(q));
        ans = query(q);
        if(ans==n)return;
        if(!ans)break;
    }
    cnt = 0;
    vector<pair<int, int>>par;
    vector<int>unknown;
    
    FOR(i, 2, n, 1){
        swap(q[0], q[i-1]);
        sum = query(q);
        if(sum==n)return;
        if(sum==2){
            b[1] = b[i] = 1;
            ans+=2;
            break;
        }
        if(sum==1)v.pb(i);
        swap(q[0], q[i-1]);
    }
    for(auto i : v){
        swap(q[i-1], q[0]);
        if(i != 2)swap(q[0], q[1]);
        else swap(q[0], q[2]);
        k = query(q);
        if(k == n)return;
        if(k == 0){
            b[1] = 1;
            if(i != 2)swap(q[0], q[1]);
            else swap(q[0], q[2]);
            ans++;
            break;
        }
        if(i != 2)swap(q[0], q[1]);
        else swap(q[0], q[2]);
        swap(q[i-1], q[0]);
    }
    while(cnt != n){
        
        par.clear();
        unknown.clear();
        
    FOR(i,1,n,1){
        if(!b[i])unknown.pb(i);
    }
    
    while(1){
    random_shuffle(all(unknown));
    FOR(i, 1, unknown.sz-1, 2)swap(q[unknown[i]-1], q[unknown[i-1]-1]);
    sum = query(q);
    if(sum==n)return;
    if(sum>ans)break;
    FOR(i, 1, unknown.sz-1, 2)swap(q[unknown[i]-1], q[unknown[i-1]-1]);
    }
    FOR(i, 1, unknown.sz-1, 2)par.pb({ unknown[i]-1, unknown[i-1]-1 });
    l = 0, r = par.sz-1;
    res = 0;
    while(l <= r){
        int md = (l + r) >> 1;
        FOR(i, md+1, r, 1){
            swap(q[par[i].S], q[par[i].F]);
        }
        sum = query(q);
        if(sum==n)return;
        if(sum == ans){
        FOR(i, md+1, r, 1){
            swap(q[par[i].S], q[par[i].F]);
        }
        FOR(i, l, md, 1)swap(q[par[i].S], q[par[i].F]);
        l = md + 1;
        }
        else r = md - 1, res = md;
    }
    swap(q[0], q[par[res].F]);
    sum = query(q);
    if(sum==n)return;
    if(sum == ans - 2)cnt++, b[par[res].F] = 1, ans++;
    swap(q[0], q[par[res].F]);
    swap(q[0], q[par[res].S]);
    sum = query(q);
    if(sum == n)return;
    if(sum == ans - 2)cnt++, b[par[res].S] = 1, ans++;
    swap(q[0], q[par[res].S]);
    }
    query(q);
}

• Subtask 1: 9 / 13
• Subtask 2: 0 / 38
• Subtask 3: 0 / 49