oj.uz

Submission #1082590

# Submission time Handle Problem Language Result Execution time Memory
1082590 2024-08-31T16:54:43 Z juicy Zagonetka (COI18_zagonetka) C++17
100 / 100
 106 ms 1016 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 23 ms 504 KB Output is correct
3 Correct 29 ms 600 KB Output is correct
4 Correct 33 ms 512 KB Output is correct
5 Correct 10 ms 344 KB Output is correct
6 Correct 41 ms 592 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 27 ms 512 KB Output is correct
10 Correct 15 ms 344 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 344 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 760 KB Output is correct
2 Correct 106 ms 596 KB Output is correct
3 Correct 68 ms 604 KB Output is correct
4 Correct 33 ms 532 KB Output is correct
5 Correct 45 ms 528 KB Output is correct
6 Correct 65 ms 344 KB Output is correct
7 Correct 38 ms 344 KB Output is correct
8 Correct 57 ms 604 KB Output is correct
9 Correct 51 ms 528 KB Output is correct
10 Correct 99 ms 768 KB Output is correct
11 Correct 80 ms 516 KB Output is correct
12 Correct 80 ms 516 KB Output is correct
13 Correct 89 ms 1016 KB Output is correct
14 Correct 81 ms 600 KB Output is correct
15 Correct 96 ms 588 KB Output is correct
16 Correct 85 ms 508 KB Output is correct