Submission #724964

#	Time	Username	Problem	Language	Result	Execution time	Memory
724964		lukadupli	Zagonetka (COI18_zagonetka)	C++14	18 / 100	358 ms	560 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);
}

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