oj.uz

Submission #724964

# Submission time Handle Problem Language Result Execution time Memory
724964 2023-04-16T11:51:52 Z lukadupli Zagonetka (COI18_zagonetka) C++14
18 / 100
 358 ms 560 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 105;

int n, arr[MAXN];
int maybe[MAXN][MAXN], sure[MAXN][MAXN];

int mini[MAXN], maxi[MAXN];

bool query(int* perm, int len){
    cout << "query ";
    for(int i = 0; i < len; i++) cout << perm[i] << ' ';
    cout << endl;

    bool ans;
    cin >> ans;

    return ans;
}

bool bio[MAXN];
vector<int> topsort;
void dfs(int node){
    bio[node] = 1;
    for(int i = 0; i < n; i++){
        if(!bio[i] && (maybe[node][i] || sure[node][i])) dfs(i);
    }

    topsort.push_back(node);
}

vector<pair<int, int>> edgesort;
void edfs(int node){
    bio[node] = 1;
    for(int i = 0; i < n; i++){
        if(maybe[node][i] || sure[node][i]){
            if(!bio[i]) edfs(i);
        }
    }

    for(int i = 0; i < n; i++){
        if(maybe[i][node]) edgesort.push_back({i, node});
    }
}

void gentopsort(){
    memset(bio, 0, sizeof bio);
    topsort.clear();
    for(int i = 0; i < n; i++) if(!bio[i]) dfs(i);
    reverse(topsort.begin(), topsort.end());
}
void genedgesort(){
    memset(bio, 0, sizeof bio);
    edgesort.clear();
    for(int i = 0; i < n; i++) if(!bio[i]) edfs(i);
    reverse(edgesort.begin(), edgesort.end());
}

int perm[MAXN];
void genperm(){
    gentopsort();
    for(int i = 0; i < n; i++) perm[topsort[i]] = i + 1;
}

void solve_edge(){
    genedgesort();
    int a = edgesort[0].first;
    int b = edgesort[0].second;

    maybe[a][b] = 0;
    maybe[b][a] = 1;
    genperm();

    if(!query(perm, n)){
        sure[a][b] = 1;
    }
    maybe[b][a] = 0;
}

void gen_small(const vector<int>& v, int a, int b){
    if(v.empty()) return;

    vector<int> sub, nsub;

    int small = v[0];
    for(int e : v){
        if(e == small) continue;
        if(sure[small][e] == -1) sub.push_back(e);
        else nsub.push_back(e);
    }

    mini[small] = a + sub.size();
    gen_small(sub, a, a + sub.size() - 1);
    gen_small(nsub, a + sub.size() + 1, b);
}
void gen_big(const vector<int>& v, int a, int b){
    if(v.empty()) return;

    vector<int> sub, nsub;

    int small = v[0];
    for(int e : v){
        if(e == small) continue;
        if(sure[small][e] == 1) sub.push_back(e);
        else nsub.push_back(e);
    }

    maxi[small] = b - sub.size();
    gen_big(sub, b - sub.size() + 1, b);
    gen_big(nsub, a, b - sub.size() - 1);
}

int last;
void dfs1(int node){
    for(int nxt = 0; nxt < n; nxt++){
        if(sure[node][nxt] == -1 && !mini[nxt]) dfs1(nxt);
    }

    mini[node] = ++last;
}

void dfs2(int node){
    for(int nxt = 0; nxt < n; nxt++){
        if(sure[node][nxt] == 1 && !maxi[nxt]) dfs2(nxt);
    }

    maxi[node] = --last;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];

    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(arr[i] < arr[j]) maybe[i][j] = 1;
            else maybe[j][i] = 1;
        }
    }

    for(int i = 0; i < n * (n - 1) / 2; i++) solve_edge();

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) if(sure[i][j] == 1) sure[j][i] = -1;
    }

    /*last = 0;
    for(int i = 0; i < n; i++){
        if(!mini[i]) dfs1(i);
    }

    last = n + 1;
    for(int i = 0; i < n; i++){
        if(!maxi[i]) dfs2(i);
    }*/

    vector<int> v;
    for(int i = 0; i < n; i++) v.push_back(i);

    gen_small(v, 1, n);
    gen_big(v, 1, n);

    cout << "end\n";
    for(int i = 0; i < n; i++) cout << mini[i] << ' ';
    cout << '\n';
    for(int i = 0; i < n; i++) cout << maxi[i] << ' ';
    cout << endl;

	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Incorrect 0 ms 208 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 25 ms 316 KB Output is correct
2 Correct 76 ms 360 KB Output is correct
3 Correct 95 ms 364 KB Output is correct
4 Correct 120 ms 368 KB Output is correct
5 Correct 18 ms 336 KB Output is correct
6 Correct 106 ms 368 KB Output is correct
7 Correct 8 ms 328 KB Output is correct
8 Correct 9 ms 336 KB Output is correct
9 Correct 80 ms 352 KB Output is correct
10 Correct 33 ms 336 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 560 KB Output is correct
2 Correct 358 ms 456 KB Output is correct
3 Correct 311 ms 392 KB Output is correct
4 Incorrect 352 ms 552 KB Output isn't correct
5 Halted 0 ms 0 KB -