oj.uz

Submission #247352

# Submission time Handle Problem Language Result Execution time Memory
247352 2020-07-11T08:56:01 Z lyc Mouse (info1cup19_mouse) C++14
13 / 100
 25 ms 528 KB 
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

int ask(vector<int>& q) { return query(q); }

const int mxN = 257;

int N;
int am[mxN][mxN];
vector<int> al[mxN];

bool vis[mxN];

vector<int> p, q, ans;

vector<int> getcyc(int u, int i) {
    vector<int> cyc = { u, al[u][0] };
    u = al[u][0];
    while (1) {
        for (int v : al[u]) if (v != cyc[SZ(cyc)-2]) {
            u = v;
            break;
        }
        if (u == cyc[0]) break;
        else cyc.push_back(u);
    }
    return cyc;
}

void solve(int n) {
    N = n;
    p.assign(N,0); ans.assign(N,-1);
    iota(ALL(p),1);
    int r = ask(p);
    if (r == N) return;
    FOR(i,0,N-1) if (ans[i] == -1) {
        bool ok = 1;
        FOR(j,0,N-1) if (i != j) {
            int v;
            if (j < i) v = am[j][i];
            else {
                swap(p[i],p[j]);
                v = am[i][j] = ask(p);
                swap(p[i],p[j]);
            }
            if (v-r >= 0) ok = 0;
        }
        if (ok) {
            ans[i] = p[i];
            FOR(j,0,N-1) if (i != j) {
                int v = (j < i ? am[j][i] : am[i][j]);
                if (v-r == -2) ans[j] = p[j];
            }
        } else {
            FOR(j,0,N-1) if (i != j) {
                int v = (j < i ? am[j][i] : am[i][j]);
                if (v-r == -1) ans[j] = p[j];
                else if (v-r == 1) {
                    al[i].push_back(j);
                    al[j].push_back(i);
                }
                else if (v-r == 2) ans[i] = p[j], ans[j] = p[i];
            }
        }
    }

    //FOR(i,0,N-1){ FOR(j,0,N-1){ cout << am[i][j] << ' '; } cout << endl; }

    FOR(i,0,N-1) if (ans[i] != -1) p[i] = ans[i];

    memset(vis,0,sizeof vis);
    q.assign(N,0);
    FOR(i,0,N-1) q[i] = p[i];
    FOR(i,0,N-1) if (!vis[i] && SZ(al[i])) {
        auto x = getcyc(i,i);
        FOR(i,0,SZ(x)-1) {
            q[x[i]] = p[x[(i+1)%SZ(x)]];
            vis[x[i]] = 1;
        }
    }

    //FOR(i,0,N-1) cout << q[i] << ' ';
    //cout << endl;

    int s = ask(q);
    if (s == N) return;

    memset(vis,0,sizeof vis);
    FOR(i,0,N-1) if (!vis[i] && SZ(al[i])) {
        int u = i;
        auto x = getcyc(i,i);
        reverse(ALL(x));
        FOR(i,0,SZ(x)-1) {
            q[x[i]] = p[x[(i+1)%SZ(x)]];
            vis[x[i]] = 1;
        }
        int t = ask(q);
        if (t == N) return;
        if (t < s) {
            reverse(ALL(x));
            FOR(i,0,SZ(x)-1) {
                q[x[i]] = p[x[(i+1)%SZ(x)]];
            }
        }
    }

    //FOR(i,0,N-1) cout << ans[i] << ' ';
    //cout << endl;
}

Compilation message

mouse.cpp: In function 'void solve(int)':
mouse.cpp:98:13: warning: unused variable 'u' [-Wunused-variable]
         int u = i;
             ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Correct! Number of queries: 24
2 Correct 5 ms 256 KB Correct! Number of queries: 8
3 Correct 5 ms 468 KB Correct! Number of queries: 17
4 Correct 5 ms 384 KB Correct! Number of queries: 23
5 Correct 6 ms 384 KB Correct! Number of queries: 20
6 Correct 5 ms 384 KB Correct! Number of queries: 16

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Correct! Number of queries: 24
2 Correct 5 ms 256 KB Correct! Number of queries: 8
3 Correct 5 ms 468 KB Correct! Number of queries: 17
4 Correct 5 ms 384 KB Correct! Number of queries: 23
5 Correct 6 ms 384 KB Correct! Number of queries: 20
6 Correct 5 ms 384 KB Correct! Number of queries: 16
7 Correct 22 ms 384 KB Correct! Number of queries: 1300
8 Correct 24 ms 384 KB Correct! Number of queries: 1300
9 Correct 24 ms 528 KB Correct! Number of queries: 1100
10 Correct 25 ms 384 KB Correct! Number of queries: 1300
11 Correct 21 ms 384 KB Correct! Number of queries: 900
12 Correct 24 ms 384 KB Correct! Number of queries: 1200
13 Correct 23 ms 384 KB Correct! Number of queries: 1100
14 Correct 23 ms 384 KB Correct! Number of queries: 1200
15 Correct 23 ms 504 KB Correct! Number of queries: 1300
16 Incorrect 20 ms 384 KB Is not a permutation

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Correct! Number of queries: 24
2 Correct 5 ms 256 KB Correct! Number of queries: 8
3 Correct 5 ms 468 KB Correct! Number of queries: 17
4 Correct 5 ms 384 KB Correct! Number of queries: 23
5 Correct 6 ms 384 KB Correct! Number of queries: 20
6 Correct 5 ms 384 KB Correct! Number of queries: 16
7 Correct 22 ms 384 KB Correct! Number of queries: 1300
8 Correct 24 ms 384 KB Correct! Number of queries: 1300
9 Correct 24 ms 528 KB Correct! Number of queries: 1100
10 Correct 25 ms 384 KB Correct! Number of queries: 1300
11 Correct 21 ms 384 KB Correct! Number of queries: 900
12 Correct 24 ms 384 KB Correct! Number of queries: 1200
13 Correct 23 ms 384 KB Correct! Number of queries: 1100
14 Correct 23 ms 384 KB Correct! Number of queries: 1200
15 Correct 23 ms 504 KB Correct! Number of queries: 1300
16 Incorrect 20 ms 384 KB Is not a permutation