Submission #643560

#	Time	Username	Problem	Language	Result	Execution time	Memory
643560		kebine	Zagonetka (COI18_zagonetka)	C++17	9 / 100	8 ms	428 KiB

zagonetka

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int n, a[N], mx[N], mn[N], deg[N], Deg[N];

int main()
{
  cin.tie(0); ios_base::sync_with_stdio(0);

  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];

  if(n <= 6) {
    vector<int> p, mx, mn;
    for(int i = 1; i <= n; i++) p.push_back(i);
    do {
      cout << "query ";
      for(int i = 0; i < n; i++) {
        cout << p[i] << " ";
      }
      cout << endl;

      int x; cin >> x;
      if(x) {
        if(mx.empty()) {
          mx = p;
        } else {
          if(p > mx) mx = p;
        }
        if(mn.empty()) mn = p;
        else if(p < mn) mn = p;
      }
    } while(next_permutation(p.begin(), p.end()));

    cout << "end\n";
    for(auto i : mn) cout << i << " ";
    cout << '\n';
    for(auto i : mx) cout << i << " ";
    cout << endl;
  } else {
    vector<pair<int,int>> edges;
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++) {
        if(i == j) continue;
        if(a[i] < a[j]) {
          edges.push_back({i, j});
        }
      }  
    }

    vector<int> g[n + 1];

    for(auto [l, r] : edges) {
      swap(a[l], a[r]);
      cout << "query ";
      for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl;
      int x; cin >> x;
      if(!x) {
        g[l].push_back(r);
        deg[r]++;
        Deg[r]++;
        break;
      }
      swap(a[l], a[r]);
    }

    priority_queue<int> q;
    for(int i = 1; i <= n; i++) if(!deg[i]) q.push(i);
    int cnt = 0;
    while(!q.empty()) {
      int v = q.top(); q.pop();
      mx[v] = ++cnt;
      for(auto u : g[v]) {
        deg[u]--;
        if(deg[u] == 0) {
          q.push(u);
        }
      }
    }

    for(int i = 1; i <= n; i++) if(!Deg[i]) q.push(-i);

    cnt = 0;
    while(!q.empty()) {
      int v = q.top(); q.pop();
      v = -v;
      mn[v] = ++cnt;
      for(auto u : g[v]) {
        Deg[u]--;
        if(Deg[u] == 0) {
          q.push(-u);
        }
      }
    }

    cout << "end\n";
    for(int i = 1; i <= n; i++) cout << mn[i] << " ";
    cout << '\n';
    for(int i = 1; i <= n; i++) cout << mx[i] << " ";
    cout << endl;
   }

}

Compilation message (stderr)

zagonetka.cpp: In function 'int main()':
zagonetka.cpp:57:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   57 |       for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl;
      |       ^~~
zagonetka.cpp:57:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   57 |       for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl;
      |                                                        ^~~~

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