Submission #421784

#	Time	Username	Problem	Language	Result	Execution time	Memory
421784		rama_pang	Zagonetka (COI18_zagonetka)	C++17	100 / 100	101 ms	396 KiB

zagonetka

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

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

  int N;
  cin >> N;
  vector<int> P(N);
  for (int i = 0; i < N; i++) {
    cin >> P[i];
    P[i]--;
  }

  const auto Query = [&](vector<int> a) {
    cout << "query";
    for (auto i : a) cout << ' ' << i + 1;
    cout << endl;
    int foo;
    cin >> foo;
    return foo;
  };

  vector<int> active;
  vector<vector<int>> adj(N);
  for (int add = 0; add < N; add++) {
    int pos = -1;
    for (int i = 0; i < N; i++) {
      if (P[i] == add) {
        pos = i;
        break;
      }
    }
    assert(pos != -1);
    for (int _a = int(active.size()) - 1; _a >= 0; _a--) {
      int x = active[_a];
      vector<int> que = {x};
      vector<int> vis(N); vis[x] = 1;
      for (int i = 0; i < int(que.size()); i++) {
        int u = que[i];
        for (auto v : adj[u]) if (!vis[v]) {
          vis[v] = 1;
          que.emplace_back(v);
        }
      }
      bool found = false;
      for (auto y : que) {
        if (!adj[y].empty() && adj[y].back() == pos) {
          found = true;
          break;
        }
      }
      if (found) {
        adj[x].emplace_back(pos);
        continue;
      }
      sort(begin(que), end(que), [&](int i, int j) {
        return P[i] > P[j];
      });
      int elem = add;
      vector<int> Q = P;
      for (auto y : que) {
        Q[y] = elem--;
      }
      Q[pos] = elem--;
      vector<int> others;
      for (auto y : active) {
        if (!vis[y]) {
          others.emplace_back(y);
        }
      }
      sort(begin(others), end(others), [&](int i, int j) {
        return P[i] > P[j];
      });
      for (auto y : others) {
        Q[y] = elem--;
      }
      if (!Query(Q)) {
        adj[x].emplace_back(pos);
      }
    }
    active.emplace_back(pos);
  }

  vector<pair<int, int>> edges;
  for (int i = 0; i < N; i++) {
    for (auto j : adj[i]) {
      edges.emplace_back(i, j);
    }
  }

  const auto Solve = [&]() -> vector<int> {
    vector<vector<int>> can(N, vector<int>(N));
    for (auto [u, v] : edges) {
      can[u][v] = 1;
    }
    for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          can[i][j] |= can[i][k] && can[k][j];
        }
      }
    }
    int label = 0;
    vector<int> res(N, -1);
    const auto Dfs = [&](const auto &self, int u) {
      if (res[u] != -1) return;
      for (int v = 0; v < N; v++) if (can[v][u]) {
        self(self, v);
      }
      res[u] = label++;
    };
    for (int i = 0; i < N; i++) if (res[i] == -1) {
      Dfs(Dfs, i);
    }
    return res;
  };

  vector<int> ansSml = Solve();
  for (auto &[u, v] : edges) swap(u, v);
  vector<int> ansBig = Solve();
  for (auto &a : ansBig) a = N - 1 - a;

  cout << "end\n";
  for (int i = 0; i < N; i++) cout << ansSml[i] + 1 << " \n"[i + 1 == N];
  for (int i = 0; i < N; i++) cout << ansBig[i] + 1 << " \n"[i + 1 == N];
  cout << flush;
  return 0;
}

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