Submission #749270

#	Time	Username	Problem	Language	Result	Execution time	Memory
749270		Username4132	Zagonetka (COI18_zagonetka)	C++14	100 / 100	100 ms	416 KiB

zagonetka

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back

const int MAXN=110;
int n, reply;
bool vis[MAXN], blocked[MAXN];
vector<int> arr, rev, g[MAXN], net[MAXN], net_rev[MAXN], ord, reach;

vector<int> inv(vector<int>& per){
    vector<int> ret(per.size());
    forn(i, per.size()) ret[per[i]]=i;
    return ret;
}

void dfs(int v){
    vis[v]=true;
    for(int to:g[v]) if(!vis[to]) dfs(to);
    ord.PB(v);
}

void dfs2(int v, vector<int>* gr){
    blocked[v]=true;
    for(int to:gr[v]) if(!blocked[to]) dfs2(to, gr);
    reach.PB(v);
}

vector<int> opt(vector<int> v, vector<int>* gr){
    if(v.size()<=1) return v;
    auto itr = min_element(v.begin(), v.end());
    forn(i, n) blocked[i]=true;
    for(auto el:v) blocked[el]=false;
    reach.clear();
    dfs2(*itr, gr);
    for(int el:v) blocked[el]=false;
    for(int re:reach) blocked[re]=true;
    vector<int> l, r;
    for(int el:v){
        if(el==*itr) continue;
        if(blocked[el]) r.PB(el);
        else l.PB(el);
    }
    vector<int> lv = opt(l, gr);
    vector<int> rv = opt(r, gr);
    lv.PB(*itr);
    lv.insert(lv.end(), rv.begin(), rv.end());
    return lv;
}

int main(){
    scanf("%d", &n);
    arr.resize(n);
    forn(i, n) scanf("%d", &arr[i]), --arr[i];
    rev = inv(arr);
    dforn(i, n){
        forsn(j, i+1, n) g[i].PB(j);
        forsn(j, i+1, n){
            g[i].erase(find(g[i].begin(), g[i].end(), j));
            forsn(k, i, n) vis[k]=false;
            forsn(k, i, n) if(!vis[k]) dfs(k);
            reverse(ord.begin(), ord.end());
            vector<int> cr(n);
            forn(k, n) cr[k]=rev[k<i? k : ord[k-i]];
            vector<int> ask = inv(cr);
            printf("query");
            forn(k, n) printf(" %d", ask[k]+1);
            printf("\n");
            fflush(stdout);
            scanf("%d", &reply);
            if(!reply) g[i].PB(j);
            ord.clear();
        }
    }

    vector<int> alln;
    forn(i, n) alln.PB(i);
    forn(v, n) for(int to:g[v]) net[rev[v]].PB(rev[to]), net_rev[rev[to]].PB(rev[v]);

    vector<int> ans1 = opt(alln, net_rev);
    reverse(ans1.begin(), ans1.end());
    vector<int> ans2 = opt(alln, net);
    vector<int> ret1 = inv(ans1), ret2 = inv(ans2);
    printf("end\n");
    forn(i, n) printf("%d ", ret1[i]+1);
    printf("\n");
    forn(i, n) printf("%d ", ret2[i]+1);
    printf("\n");
    fflush(stdout);
}

Compilation message (stderr)

zagonetka.cpp: In function 'int main()':
zagonetka.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
zagonetka.cpp:58:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     forn(i, n) scanf("%d", &arr[i]), --arr[i];
      |                ~~~~~^~~~~~~~~~~~~~~
zagonetka.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |             scanf("%d", &reply);
      |             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 51 / 51