답안 #47795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47795 2018-05-07T09:49:09 Z qoo2p5 Zagonetka (COI18_zagonetka) C++17
100 / 100
145 ms 720 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = 101;

int n;
vector<int> p;
int pos[N];
bool e[N][N];

bool ask(vector<int> q) {
    cout << "query ";
    for (int i : q) {
        cout << i << " ";
    }
    cout << endl;
    int x;
    cin >> x;
    return x;
}

bool conn(int u, int v) {
    return e[u][v] || e[v][u];
}

bool cool[N];
bool vis[N];

void dfs(int v, vector<int> &st) {
    vis[v] = 1;
    rep(u, 0, n) {
        if (!cool[u] || !e[v][u] || vis[u]) {
            continue;
        }
        dfs(u, st);
    }
    st.pb(v);
}

void run() {
    cin >> n;
    p.resize(n);
    rep(i, 0, n) {
        cin >> p[i];
        e[i][i] = 1;
        pos[p[i]] = i;
    }
    rep(len, 1, n) {
        rep(i, 1, n + 1) {
            int j = i + len;
            if (j > n) {
                break;
            }
            
            int a = pos[i];
            int b = pos[j];
            
            if (conn(a, b)) {
                continue;
            }
            
            vector<int> A, B, C;
            memset(cool, 0, sizeof cool);
            memset(vis, 0, sizeof vis);
            vector<int> yeah;
            rep(t, 0, n) {
                if (i <= p[t] && p[t] <= j) {
                    if (conn(a, t)) {
                        assert(!conn(b, t));
                        A.pb(t);
                    } else if (conn(b, t)) {
                        B.pb(t);
                    } else {
                        C.pb(t);
                    }
                    cool[t] = 1;
                    yeah.pb(p[t]);
                }
            }
            sort(all(yeah));
            
            vector<int> SA, SB, SC;
            for (int v : A) {
                if (!vis[v]) {
                    dfs(v, SA);
                }
            }
            for (int v : B) {
                if (!vis[v]) {
                    dfs(v, SB);
                }
            }
            for (int v : C) {
                if (!vis[v]) {
                    dfs(v, SC);
                }
            }

            vector<int> q = p;
            for (int v : SA) {
                q[v] = yeah.back();
                yeah.pop_back();
            }
            for (int v : SB) {
                q[v] = yeah.back();
                yeah.pop_back();
            }
            for (int v : SC) {
                q[v] = yeah.back();
                yeah.pop_back();
            }
            
            if (!ask(q)) {
                e[a][b] = 1;
                rep(iter, 0, 2) {
                    rep(u, 0, n) {
                        rep(v, 0, n) {
                            e[u][v] |= e[u][a] && e[a][v];
                        }
                    }
                    rep(u, 0, n) {
                        rep(v, 0, n) {
                            e[u][v] |= e[u][b] && e[b][v];
                        }
                    }
                }
            }
        }
    }
    cout << "end" << endl;
    
    /*rep(i, 0, n) {
        rep(j, 0, n) {
            if (e[i][j] && i != j) {
                cerr << i << " " << j << endl;
            }
        }
    }*/
    
    {
        vector<int> res(n);
        function<void(vector<int> pos, int ptr)> f = [&] (vector<int> pos, int ptr) {
            if (!sz(pos)) {
                return;
            }
            vector<int> pos_sh = pos;
            pos_sh.erase(pos_sh.begin());
            int v = pos[0];
            if (!res[v]) {
                vector<int> nxt;
                for (int p : pos_sh) {
                    if (!res[p] && e[p][v]) {
                        nxt.pb(p);
                    }
                }
                res[v] = ptr + sz(nxt);
                f(nxt, ptr);
                ptr += (1 + sz(nxt));
            }
            
            f(pos_sh, ptr);
        };
        vector<int> pos(n);
        rep(i, 0, n) {
            pos[i] = i;
        }
        f(pos, 1);
        for (int v : res) {
            cout << v << " ";
        }
        cout << endl;
    }
    
    {
        vector<int> res(n);
        function<void(vector<int> pos, int ptr)> f = [&] (vector<int> pos, int ptr) {
            if (!sz(pos)) {
                return;
            }
            vector<int> pos_sh = pos;
            pos_sh.erase(pos_sh.begin());
            int v = pos[0];
            if (!res[v]) {
                vector<int> nxt;
                for (int p : pos_sh) {
                    if (!res[p] && e[v][p]) {
                        nxt.pb(p);
                    }
                }
                res[v] = ptr - sz(nxt);
                f(nxt, ptr);
                ptr -= (1 + sz(nxt));
            }
            
            f(pos_sh, ptr);
        };
        vector<int> pos(n);
        rep(i, 0, n) {
            pos[i] = i;
        }
        f(pos, n);
        for (int v : res) {
            cout << v << " ";
        }
        cout << endl;
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 516 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 516 KB Output is correct
7 Correct 2 ms 516 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 528 KB Output is correct
2 Correct 35 ms 640 KB Output is correct
3 Correct 43 ms 640 KB Output is correct
4 Correct 51 ms 640 KB Output is correct
5 Correct 9 ms 640 KB Output is correct
6 Correct 51 ms 640 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 10 ms 640 KB Output is correct
9 Correct 37 ms 640 KB Output is correct
10 Correct 20 ms 640 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 700 KB Output is correct
9 Correct 7 ms 700 KB Output is correct
10 Correct 3 ms 700 KB Output is correct
11 Correct 5 ms 700 KB Output is correct
12 Correct 6 ms 700 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 700 KB Output is correct
2 Correct 135 ms 716 KB Output is correct
3 Correct 106 ms 716 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 8 ms 716 KB Output is correct
6 Correct 8 ms 716 KB Output is correct
7 Correct 34 ms 716 KB Output is correct
8 Correct 73 ms 716 KB Output is correct
9 Correct 52 ms 716 KB Output is correct
10 Correct 132 ms 716 KB Output is correct
11 Correct 114 ms 716 KB Output is correct
12 Correct 110 ms 716 KB Output is correct
13 Correct 134 ms 716 KB Output is correct
14 Correct 119 ms 720 KB Output is correct
15 Correct 145 ms 720 KB Output is correct
16 Correct 130 ms 720 KB Output is correct