oj.uz

Submission #724929

# Submission time Handle Problem Language Result Execution time Memory
724929 2023-04-16T10:09:05 Z lukadupli Zagonetka (COI18_zagonetka) C++14
0 / 100
 159 ms 344 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);
}

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

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

void solve_edge(){
    gentopsort();
    int a, b;
    bool found = 0;
    for(int i = 0; i < topsort.size() - 1; i++){
        a = topsort[i]; b = topsort[i + 1];
        if(maybe[a][b]){
            found = 1;
            break;
        }
    }

    if(!found) return;

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

Compilation message

zagonetka.cpp: In function 'void solve_edge()':
zagonetka.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < topsort.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 324 KB Output is correct
2 Correct 42 ms 328 KB Output is correct
3 Correct 48 ms 316 KB Output is correct
4 Correct 44 ms 332 KB Output is correct
5 Incorrect 36 ms 208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -