oj.uz

Submission #724939

# Submission time Handle Problem Language Result Execution time Memory
724939 2023-04-16T11:01:41 Z lukadupli Zagonetka (COI18_zagonetka) C++14
27 / 100
 465 ms 648 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;
}

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);
    }

    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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 332 KB Output is correct
2 Correct 70 ms 336 KB Output is correct
3 Correct 93 ms 360 KB Output is correct
4 Correct 93 ms 376 KB Output is correct
5 Correct 18 ms 332 KB Output is correct
6 Correct 95 ms 376 KB Output is correct
7 Correct 8 ms 328 KB Output is correct
8 Correct 11 ms 208 KB Output is correct
9 Correct 77 ms 356 KB Output is correct
10 Correct 28 ms 336 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 424 KB Output is correct
2 Correct 368 ms 436 KB Output is correct
3 Correct 269 ms 648 KB Output is correct
4 Correct 338 ms 456 KB Output is correct
5 Correct 463 ms 472 KB Output is correct
6 Correct 465 ms 472 KB Output is correct
7 Incorrect 332 ms 428 KB Output isn't correct
8 Halted 0 ms 0 KB -