제출 #315072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
315072		2qbingxuan	Mouse (info1cup19_mouse)	C++14	18.28 / 100	3022 ms	384 KiB

mouse

#ifndef local
#include "grader.h"
#endif // local
#include <bits/stdc++.h>
#ifdef local
#define debug(args...) qqbx(#args, args)
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    (std::cerr << "(" << s << ") = (" , ... , (std::cerr << args << (--cnt ? ", " : ")\n")));
}
#else
#define debug(...) ((void)0)
#endif // local
#define pb emplace_back
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;

vector<int> secret_p;
#ifdef local
int qs=0;
int query(vector<int> q) {
    ++qs;
    assert(secret_p.size() == q.size());
    int n = secret_p.size(), cnt = 0;
    for(int i = 0; i < n; i++) if(secret_p[i] == q[i]) ++cnt;
    if(cnt == n) {
        debug(qs);
        cerr << "OK!\n";
        exit(0);
    }
    return cnt;
}
#endif // local

void solve(int n) {
    vector<int> p(n);
    vector<int> ok(n);
    iota(all(p), 1);
    int qp = query(p);
    debug(qp);
    for(int i = 0; i < n; i++) cerr << p[i] << ' ';
    cerr << '\n';
    for(int t = 0; t < n*n; t++) {
        int i = t % n;
        /* vector<int> v; */
        int mn = 0;
        int pos = -1;
        for(int j = 0; j < n; j++) {
            if(j == i) continue;
            /* if(ok[j]) continue; */
            swap(p[i], p[j]);
            int x = query(p) - qp;
            swap(p[i], p[j]);
            if(x > mn) {
                pos = j;
                mn = x;
            }
            /*
            if(x == 2) {
                pos = j;
                break;
            } else if(x == -2) {
                pos = i;
                ok[j] = true;
                break;
            } else if(x == 1) {
                pos = j;
                break;
            } else if(x == -1) {
                v.pb(j);
            } else if(x != 0) {
                cerr << "QQQ\n";
            }
            */
        }
        
        if(pos != -1) {
            swap(p[i], p[pos]);
            qp = query(p);
            /* for(int j: v) ok[j] = true; */
        }
    }
    for(int i = 0; i < n; i++) cerr << p[i] << ' ';
    cerr << '\n';
}

#ifdef local
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    secret_p.resize(n);
    for(int i = 0; i < n; i++) cin >> secret_p[i];
    solve(n);
}
#endif // local

• Subtask 1: 9.000004 / 13
• Subtask 2: 9.275876 / 38
• Subtask 3: 0 / 49