oj.uz

Submission #44224

# Submission time Handle Problem Language Result Execution time Memory
44224 2018-03-30T15:36:49 Z ShadowLight Zagonetka (COI18_zagonetka) C++14
27 / 100
 3000 ms 556 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;
            while (q[pos[i]] < q[pos[j]]) {
                int v = j;
                while (gr[v].size()) {
                    int u = -1;
                    int maxk = -1;
                    for (int x : gr[v]) {
                        if (q[pos[x]] > maxk) {
                            maxk = q[pos[x]];
                            u = x;
                        }
                    }
                    assert(u != -1);
                    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 = -1, mink = INF;
                    for (int x : rev_gr[v]) {
                        if (q[pos[x]] < mink) {
                            mink = q[pos[x]];
                            u = x;
                        }
                    }
                    assert(u != -1);
                    if (q[pos[u]] > j) break;
                    swap(q[pos[v]], q[pos[u]]);
                    v = u;
                    while (gr[v].size()) {
                        int u = -1, maxk = q[pos[v]];
                        for (int x : gr[v]) {
                            if (q[pos[x]] > maxk) {
                                u = x;
                                maxk = q[pos[x]];
                            }
                        }
                        if (u == -1) 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);
    last = 0;
    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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 516 KB Output is correct
7 Correct 2 ms 516 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 516 KB Output is correct
2 Correct 27 ms 516 KB Output is correct
3 Correct 22 ms 516 KB Output is correct
4 Correct 29 ms 516 KB Output is correct
5 Correct 11 ms 540 KB Output is correct
6 Correct 37 ms 556 KB Output is correct
7 Correct 5 ms 556 KB Output is correct
8 Correct 8 ms 556 KB Output is correct
9 Correct 30 ms 556 KB Output is correct
10 Correct 15 ms 556 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 556 KB Time limit exceeded
2 Halted 0 ms 0 KB -