Submission #724929

#	Time	Username	Problem	Language	Result	Execution time	Memory
724929		lukadupli	Zagonetka (COI18_zagonetka)	C++14	0 / 100	159 ms	344 KiB

zagonetka

#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 (stderr)

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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 51