oj.uz

답안 #44197

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
44197 2018-03-30T13:33:09 Z ShadowLight Zagonetka (COI18_zagonetka) C++14
78 / 100
 90 ms 880 KB 
#include <bits/stdc++.h>
#define ll long long

#define TASKNAME ""

using namespace std;

const int INF = 1e9 + 7;
const int MAXN = 1e6 + 7;
const double EPS = 1e-8;

vector <vector <int> > gr;
vector <vector <int> > rev_gr;

int n;
vector <int> p;
vector <int> pos;

void query(vector <int> a) {
    cout << "query ";
    for (int x : a) {
        cout << x + 1 << " ";
    }
    cout << endl;
}

vector <bool> used;

vector <int> resa, resb;

void dfs(int v) {
    if (used[v]) return;
    used[v] = 1;
    for (int u : rev_gr[v]) {
        dfs(u);
    }
}

int last = 0;

void dfs1(int v) {
    if (resa[v] != -INF) return;
    vector <int> a;
    for (int u : gr[p[v]]) {
        a.push_back(pos[u]);
    }
    sort(a.begin(), a.end());
    for (int x : a) {
        dfs1(x);
    }
    resa[v] = last++;
}

void dfs2(int v) {
    if (resb[v] != -INF) return;
    vector <int> a;
    for (int u : rev_gr[p[v]]) {
        a.push_back(pos[u]);
    }
    sort(a.begin(), a.end());
    for (int x : a) {
        dfs2(x);
    }
    resb[v] = last--;
}

int main() {
    #ifdef MY
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #else
        //freopen(TASKNAME".in", "r", stdin);
        //freopen(TASKNAME".out", "w", stdout);
    #endif // MY
    cin >> n;
    p.resize(n);
    pos.resize(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
        pos[p[i]] = i;
    }
    gr.resize(n);
    rev_gr.resize(n);
    int iter = 0;
    for (int i = n - 1; i >= 0; i--) {
        used.clear();
        used.resize(n, 0);
        for (int j = i + 1; j < n; j++) {
            if (used[j]) {
                gr[j].push_back(i);
                rev_gr[i].push_back(j);
                iter++;
                continue;
            }
            auto q = p;
            int v = j;
            while (gr[v].size()) {
                int u = gr[v][0];
                swap(q[pos[v]], q[pos[u]]);
                v = u;
            }
            swap(q[pos[v]], q[pos[i]]);
            v = i;
            while (rev_gr[v].size()) {
                int u = rev_gr[v][0];
                if (u > j) break;
                swap(q[pos[v]], q[pos[u]]);
                v = u;
            }
            query(q);
            int ans;
            cin >> ans;
            if (!ans) {
                gr[j].push_back(i);
                rev_gr[i].push_back(j);
               //cout << j << " " << i << "\n";
                dfs(j);
                iter++;
            }
        }
    }
    resa.resize(n, -INF);
    resb.resize(n, -INF);
    for (int v = 0; v < n; v++) {
        if (resa[v] == -INF) {
            dfs1(v);
        }
    }
    last = n - 1;
    for (int v = 0; v < n; v++) {
        if (resb[v] == -INF) {
            dfs2(v);
        }
    }
    query(resa);
    query(resb);
    int ans1, ans2;
    cin >> ans1 >> ans2;
    assert(ans1 && ans2);
    cout << "end" << endl;
    for (int x : resa) {
        assert(x != -INF);
        cout << x + 1 << " ";
    }
    cout << endl;
    for (int x : resb) {
        assert(x != -INF);
        cout << x + 1 << " ";
    }
    cout << endl;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 2 ms 476 KB Output is correct
7 Correct 2 ms 476 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 476 KB Output is correct
2 Correct 31 ms 496 KB Output is correct
3 Correct 41 ms 496 KB Output is correct
4 Correct 34 ms 504 KB Output is correct
5 Correct 9 ms 504 KB Output is correct
6 Correct 35 ms 504 KB Output is correct
7 Correct 8 ms 504 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 29 ms 504 KB Output is correct
10 Correct 21 ms 512 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 552 KB Output is correct
3 Correct 5 ms 560 KB Output is correct
4 Runtime error 5 ms 684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 684 KB Output is correct
2 Correct 79 ms 684 KB Output is correct
3 Correct 71 ms 880 KB Output is correct
4 Correct 4 ms 880 KB Output is correct
5 Correct 5 ms 880 KB Output is correct
6 Correct 5 ms 880 KB Output is correct
7 Correct 16 ms 880 KB Output is correct
8 Correct 28 ms 880 KB Output is correct
9 Correct 22 ms 880 KB Output is correct
10 Correct 84 ms 880 KB Output is correct
11 Correct 53 ms 880 KB Output is correct
12 Correct 66 ms 880 KB Output is correct
13 Correct 70 ms 880 KB Output is correct
14 Correct 74 ms 880 KB Output is correct
15 Correct 73 ms 880 KB Output is correct
16 Correct 73 ms 880 KB Output is correct