oj.uz

Submission #643555

# Submission time Handle Problem Language Result Execution time Memory
643555 2022-09-22T12:31:12 Z kebine Zagonetka (COI18_zagonetka) C++17
0 / 100
 123 ms 336 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int n, a[N], m, deg[N], mn[N], mx[N], Deg[N], order[N];
vector<int> g[N];

vector<int> toposort() {
  vector<int> d(n + 1);
  for(int i = 1; i <= n; i++) {
    for(auto u : g[i]) {
      // cout << i << " -> " << u << endl;
      d[u]++;
    }
  }

  queue<int> q;
  for(int i = 1; i <= n; i++) {
    if(!d[i]) q.push(i);
    // cout << d[i] << " ";
  }
  // cout << endl;

  vector<int> ret(n + 1);
  int cnt = 0;
  while(!q.empty()) {
    int v = q.front(); q.pop();
    ret[v] = ++cnt;
    for(auto u : g[v]) {
      d[u]--;
      if(d[u] == 0) {
        q.push(u);
      }
    }
  }
  assert(cnt == n);
  return ret;

}

bool ask(int l, int r)
{
  
  // swap(a[order[l]], a[order[r]]);
  // for(int i = 1; i <= n; i++) cout << a[i] << " ";
  // swap(a[order[l]], a[order[r]]);

  

  auto v = toposort();
  cout << "query ";
  for(int i = 1; i <= n; i++) cout << v[i] << " ";
  cout << endl;

  int x;
  cin >> x;
  return x;
}

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

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

  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      if(a[j] > a[order[i - 1]] && (a[order[i]] == 0 || a[order[i]] > a[j])) {
        order[i] = j;
      }
    }
  }

  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
      g[order[i]].push_back(order[j]);
      deg[order[j]]++;
      Deg[order[j]]++;
    }
  }

  // for(int i = 1; i <= n; i++) cerr << order[i] << " "; cout << '\n';
  
  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
      // cout << i << " " << j << endl;
      // cout << order[i] << " " << order[j] << endl;
      auto it = find(g[order[i]].begin(), g[order[i]].end(), order[j]);
      g[order[i]].erase(it);
      g[order[j]].push_back(order[i]);
      if(!ask(i, j)) {
        auto it = find(g[order[j]].begin(), g[order[j]].end(), order[i]);
        g[order[j]].erase(it);
        g[order[i]].push_back(order[j]);
        break;
      } else {
        auto it = find(g[order[j]].begin(), g[order[j]].end(), order[i]);
        g[order[j]].erase(it);
        deg[order[j]]--;
        Deg[order[j]]--;
      }
     }  
  }

  // for(int i = 1; i <= n; i++) {
  //   for(auto v : g[i]) {
  //     cout << i << " -> " << v << '\n';
  //   }
  // }

  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;

}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Incorrect 1 ms 208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -