oj.uz

답안 #44188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
44188 2018-03-30T10:21:58 Z ShadowLight Zagonetka (COI18_zagonetka) C++14
78 / 100
 99 ms 608 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];
                assert(u != j);
                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);
        }
    }
    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 436 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 528 KB Output is correct
2 Correct 38 ms 536 KB Output is correct
3 Correct 32 ms 572 KB Output is correct
4 Correct 36 ms 572 KB Output is correct
5 Correct 13 ms 572 KB Output is correct
6 Correct 33 ms 572 KB Output is correct
7 Correct 6 ms 572 KB Output is correct
8 Correct 7 ms 572 KB Output is correct
9 Correct 29 ms 572 KB Output is correct
10 Correct 10 ms 572 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 572 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 6 ms 584 KB Output is correct
4 Incorrect 6 ms 584 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 584 KB Output is correct
2 Correct 99 ms 584 KB Output is correct
3 Correct 76 ms 584 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 15 ms 608 KB Output is correct
8 Correct 39 ms 608 KB Output is correct
9 Correct 23 ms 608 KB Output is correct
10 Correct 75 ms 608 KB Output is correct
11 Correct 69 ms 608 KB Output is correct
12 Correct 68 ms 608 KB Output is correct
13 Correct 58 ms 608 KB Output is correct
14 Correct 53 ms 608 KB Output is correct
15 Correct 75 ms 608 KB Output is correct
16 Correct 74 ms 608 KB Output is correct