Submission #1082590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082590		juicy	Zagonetka (COI18_zagonetka)	C++17	100 / 100	106 ms	1016 KiB

zagonetka

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 105;
 
int n, lab;
bool flg;
int a[N], p[N], memo[N][N], deg[N], res[N], pos[N];
bool e[N][N], vis[N];
 
bool cmp(int i, int j) {
  if (~memo[i][j]) {
    return memo[i][j];
  }
  if (a[i] >= a[j]) {
    return (memo[i][j] = 0);
  }
  vector<int> ver;
  for (int k = a[i]; k <= a[j]; ++k) {
    ver.push_back(pos[k]);
  }
  for (int u : ver) {
    for (int v : ver) {
      if (u != i || v != j) {
        e[u][v] = cmp(u, v);
      }
    }
  }
  e[j][i] = 1;
  queue<int> q;
  for (int u : ver) {
    deg[u] = 0;
    for (int v : ver) {
      deg[u] += e[v][u];
    }
    if (!deg[u]) {
      q.push(u);
    }
  }
  for (int k = 1; k <= n; ++k) {
    p[k] = a[k];
  }
  int c = a[i];
  while (q.size()) {
    int u = q.front(); q.pop();
    p[u] = c++;
    for (int v : ver) {
      if (e[u][v] && --deg[v] == 0) {
        q.push(v);
      }
    }
  }
  e[j][i] = 0;
  if (c <= a[j]) {
    return (memo[i][j] = 1);
  }
  cout << "query ";
  for (int i = 1; i <= n; ++i) {
    cout << p[i] << " ";
  }
  cout << endl;
  int x; cin >> x;
  return (memo[i][j] = !x);
}
 
bool hasEdge(int u, int v) {
  return flg ? cmp(u, v) : cmp(v, u);
}
 
void dfs(int u) {
  vis[u] = 1;
  for (int i = 1; i <= n; ++i) {
    if (!vis[i] && hasEdge(u, i)) {
      dfs(i);
    } 
  }
  res[u] = ++lab;
} 
 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pos[a[i]] = i;
  }
  memset(memo, -1, sizeof(memo));
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cmp(i, j);
    }
  }
  lab = 0;
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {
      dfs(i);
    }
  }
  cout << "end" << endl;
  for (int i = 1; i <= n; ++i) {
    cout << res[i] << " ";
  }
  cout << endl;
  flg = 1;
  lab = 0;
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {
      dfs(i);
    }
  }
  for (int i = 1; i <= n; ++i) {
    cout << n - res[i] + 1 << " ";
  }
  cout << endl;
  return 0;
}

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