oj.uz

Submission #44129

# Submission time Handle Problem Language Result Execution time Memory
44129 2018-03-30T07:45:47 Z ShadowLight Zagonetka (COI18_zagonetka) C++14
0 / 100
 56 ms 580 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;

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

vector <int> lvls;
vector <bool> used1;

void lvl_dfs(int v, int h) {
    if (used1[v]) return;
    used1[v] = 1;
    if (h == (int) lvls.size()) {
        lvls.push_back(-INF);
    }
    lvls[h] = max(lvls[h], v);
    for (int u : gr[v]) {
        lvl_dfs(u, h + 1);
    }
}

void rev_lvl_dfs(int v, int h) {
    if (used1[v]) return;
    used1[v] = 1;
    if (h == (int) lvls.size()) {
        lvls.push_back(INF);
    }
    lvls[h] = min(lvls[h], v);
    for (int u : rev_gr[v]) {
        rev_lvl_dfs(u, h + 1);
    }
}

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);
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
    #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);
    for (int i = n - 1; i >= 0; i--) {
        used.assign(n, 0);
        for (int j = i + 1; j < n; j++) {
            if (used[j]) {
                gr[j].push_back(i);
                rev_gr[i].push_back(j);
                continue;
            }
            auto q = p;
            int v = j;
            do {
                lvls.clear();
                used1.assign(n, 0);
                lvl_dfs(v, 0);
                if (lvls.size() == 1) break;
                for (int x = 0; x < 1; x++) {
                    swap(q[pos[lvls[x]]], q[pos[lvls[x + 1]]]);
                }
                v = lvls[1];
            } while (true);
            swap(q[pos[lvls.back()]], q[pos[i]]);
            v = i;
            do {
                lvls.clear();
                used1.assign(n, 0);
                rev_lvl_dfs(v, 0);
                if (lvls.size() == 1) break;
                for (int x = 0; x < 1; x++) {
                    swap(q[pos[lvls[x]]], q[pos[lvls[x + 1]]]);
                }
                v = lvls[1];
            } while (true);
            query(q);
            int ans;
            cin >> ans;
            if (!ans) {
                gr[j].push_back(i);
                rev_gr[i].push_back(j);
                dfs(j);
            }
        }
    }
    cout << "end" << endl;
    vector <int> resa(n), resb(n);
    set <int> q;
    vector <int> cnt(n, 0);
    for (int i = 0; i < n; i++) {
        cnt[i] = gr[i].size();
        if (!cnt[i]) {
            q.insert(pos[i]);
        }
    }
    int now = 0;
    while (!q.empty()) {
        int v = *q.begin();
        q.erase(v);
        resa[v] = now++;
        for (int u : rev_gr[p[v]]) {
            cnt[u]--;
            if (!cnt[u]) {
                q.insert(pos[u]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cnt[i] = gr[i].size();
        if (!cnt[i]) {
            q.insert(pos[i]);
        }
    }
    now = 0;
    while (!q.empty()) {
        int v = *q.rbegin();
        q.erase(v);
        resb[v] = now++;
        for (int u : rev_gr[p[v]]) {
            cnt[u]--;
            if (!cnt[u]) {
                q.insert(pos[u]);
            }
        }
    }
    for (int x : resa) {
        cout << x + 1 << " ";
    }
    cout << endl;
    for (int x : resb) {
        cout << x + 1 << " ";
    }
    cout << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 468 KB Output is correct
2 Incorrect 22 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -