oj.uz

Submission #286083

# Submission time Handle Problem Language Result Execution time Memory
286083 2020-08-30T05:32:30 Z PeppaPig Zagonetka (COI18_zagonetka) C++14
18 / 100
 104 ms 512 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 105;

int n;
int p[N], pos[N], tmp[N];
vector<int> con[N], g[N];
vector<pii> E;

vector<int> toposort(int l, int r) {
    queue<int> Q;
    vector<int> deg(n + 1), ret;
    for(int i = l; i <= r; i++) for(int x : g[pos[i]])
        ++deg[x];
    for(int i = l; i <= r; i++) if(!deg[pos[i]])
        Q.emplace(pos[i]);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        ret.emplace_back(u);
        for(int v : g[u]) if(!--deg[v])
            Q.emplace(v);
    }
    return ret;
}

bool ask() {
    vector<int> vec(n + 1);
    for(int i = 1; i <= n; i++) vec[tmp[i]] = i;
    printf("query ");
    for(int i = 1; i <= n; i++) printf("%d ", vec[i]);
    printf("\n"), fflush(stdout);
    int ret;
    scanf("%d", &ret);
    return !ret;
}

int chk[N];
set<int> cand[N];

void get_cand(int u) {
    chk[u] = true;
    for(int v : g[u]) {
        if(!chk[v]) get_cand(v);
        for(int x : cand[v]) cand[u].emplace(x);
        cand[u].emplace(v);
    }
}

void get_answer(int u, vector<int> &ans) {
    chk[u] = true;
    for(int x : cand[u]) if(!chk[x])
        get_answer(x, ans);
    ans.emplace_back(u);
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", p + i);
        pos[p[i]] = i;
    }
    for(int i = n - 1; i; i--) for(int j = i + 1; j <= n; j++) {
        for(int k = i; k <= j; k++) {
            g[pos[k]].clear();
            for(int x : con[pos[k]]) if(i <= p[x] && p[x] <= j)
                g[pos[k]].emplace_back(x);
        }
        g[pos[j]].emplace_back(pos[i]);

        vector<int> order = toposort(i, j);
        if((int)order.size() != j - i + 1) continue;
        for(int k = 1; k <= n; k++) {
            if(i <= k && k <= j) tmp[k] = order[k - i];
            else tmp[k] = pos[k];
        }
        if(ask()) con[pos[i]].emplace_back(pos[j]);
    }
    printf("end\n"), fflush(stdout);

    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        g[i].clear();
        for(int x : con[i]) g[x].emplace_back(i);
    }
    for(int i = 1; i <= n; i++) if(!chk[i]) get_cand(i);
    memset(chk, 0, sizeof chk);
    for(int i = 1; i <= n; i++) if(!chk[i]) get_answer(i, ans);
    for(int i = 1; i <= n; i++) tmp[ans[i - 1]] = i;
    for(int i = 1; i <= n; i++) printf("%d ", tmp[i]);
    printf("\n"), fflush(stdout);

    ans.clear(), memset(chk, 0, sizeof chk);
    for(int i = 1; i <= n; i++) {
        g[i].clear(), cand[i].clear();
        for(int x : con[i]) g[i].emplace_back(x);
    }
    for(int i = 1; i <= n; i++) if(!chk[i]) get_cand(i);
    memset(chk, 0, sizeof chk);
    for(int i = 1; i <= n; i++) if(!chk[i]) get_answer(i, ans);
    for(int i = 1; i <= n; i++) tmp[ans[i - 1]] = n - i + 1;
    for(int i = 1; i <= n; i++) printf("%d ", tmp[i]);
    printf("\n"), fflush(stdout);

    return 0;
}

Compilation message

zagonetka.cpp: In function 'bool ask()':
zagonetka.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |     scanf("%d", &ret);
      |     ~~~~~^~~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
zagonetka.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         scanf("%d", p + i);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 384 KB Output is correct
2 Correct 24 ms 384 KB Output is correct
3 Correct 36 ms 384 KB Output is correct
4 Correct 47 ms 384 KB Output is correct
5 Correct 13 ms 384 KB Output is correct
6 Correct 41 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 35 ms 384 KB Output is correct
10 Correct 16 ms 384 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 384 KB Output is correct
2 Correct 104 ms 384 KB Output is correct
3 Correct 88 ms 384 KB Output is correct
4 Incorrect 7 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -