제출 #1118697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118697		ikaurov	Zagonetka (COI18_zagonetka)	C++17	0 / 100	1 ms	508 KiB

zagonetka

#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
// #define endl '\n'

const int N = 500;

int g[N][N]; // g[i][j] = 1 -> p[i] > p[j]

int ask(vector<int> p){
  for (auto i : p) cout << i + 1 << " ";
  cout << endl;
  int ans;
  cin >> ans;
  return ans;
}

void answer(vector<int> p, vector<int> q){
  cout << "end" << endl;
  for (auto i : p) cout << i + 1 << " ";
  cout << endl;
  for (auto i : q) cout << i + 1 << " ";
  cout << endl;
}

int n;
vector<int> lexmin, lexmax;
int cur = 0;

void dfsmin(int i){
  if (lexmin[i] != -1) return;
  for (int j = 0; j < n; j++){
    if (g[i][j]) dfsmin(j);
  }
  lexmin[i] = cur++;
}

void dfsmax(int i){
  if (lexmax[i] != -1) return;
  for (int j = 0; j < n; j++){
    if (g[j][i]) dfsmax(j);
  }
  lexmax[i] = cur--;
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // cout.precision(20);
  cin >> n;
  vector<int> p(n), pos(n);
  for (auto &i : p){
    cin >> i;
    i--;
  }

  for (int i = 0; i < n; i++) pos[p[i]] = i;

  for (int i = 0; i < n; i++){
    // find all states with pos[i]
    vector<int> nocare, care{pos[i]};
    for (int j = i + 1; j < n; j++){
      vector<int> q = p;
      int cur = i;
      for (auto k : nocare) q[k] = cur++;
      q[pos[j]] = cur++;
      for (auto k : care) q[k] = cur++;
      g[pos[j]][pos[i]] = !ask(q);
      (g[pos[j]][pos[i]]? care : nocare).pb(pos[j]);
    }
  }

  lexmin.assign(n, -1);
  for (int i = 0; i < n; i++) dfsmin(i);

  lexmax.assign(n, -1);
  cur = n - 1;
  for (int i = 0; i < n; i++) dfsmax(i);

  answer(lexmin, lexmax);
}

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