Submission #1043914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043914		vjudge1	Zagonetka (COI18_zagonetka)	C++17	0 / 100	49 ms	416 KiB

zagonetka

#include<bits/stdc++.h>

using namespace std;

bool ask(vector<int> v)
{
  cout << "query ";
  for(int i : v)
    cout << i << ' ';
  cout << endl;
  bool res;
  cin >> res;
  return res;
}

void out(vector<int> a, vector<int> b)
{
  cout << "end\n";
  for(int i : a)
    cout << i << ' ';
  cout << endl;
  for(int i : b)
    cout << i << ' ';
  cout << endl;
  exit(0);
}

vector<int> compute(vector<vector<int> > G)
{
  int n = G.size();
  int in[n] = {};
  for(int i = 0; i < n; i ++)
    for(int j : G[i])
      in[j]++;

  vector<int> topo;
  set<int> st;

  for(int i = 0; i < n; i ++)
    if(in[i] == 0)
      st.insert(i);

  while(st.size())
    {
      int u = *st.begin();
      st.erase(st.begin());
      topo.push_back(u);

      for(int v : G[u])
	{
	  in[v]--;
	  if(in[v] == 0)
	    st.insert(v);
	}
    }

  vector<int> ans(n);
  for(int i = 0; i < n; i++)
    ans[topo[i]] = i + 1;
  return ans;
}

int main()
{
  int n;
  cin >> n;
  vector<int> p(n), idx(n + 1);
  for(int i = 0; i < n; i ++)
    {
      cin >> p[i];
      idx[p[i]] = i;
    }

  vector<vector<int> > G(n), I(n);
  
  vector<pair<int,int> > conditions;
  
  for(int v = 1; v <= n; v++)
    {
      vector<int> vec = {idx[v]};
      for(int u = v - 1; u > 0; u--)
	{
	  vector<int> q = p;
	  vec.push_back(idx[u]);
	  for(int j = 1; j < vec.size(); j++)
	    swap(q[vec[j]], q[vec[j - 1]]);
	  bool res = ask(q);
	  
	  if(res)
	    vec.pop_back();
	}
      
      for(int i = 1; i < vec.size(); i++)
	conditions.push_back({vec[0], vec[i]});
    }

  for(auto [x, y] : conditions)
    G[x].push_back(y), I[y].push_back(x);

  vector<int> a = compute(G);
  vector<int> b = compute(I);
  for(int &i : b)
    i = n - i + 1;
  
  out(a, b);
  return 0;
}

Compilation message (stderr)

zagonetka.cpp: In function 'int main()':
zagonetka.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int j = 1; j < vec.size(); j++)
      |                   ~~^~~~~~~~~~~~
zagonetka.cpp:93:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |       for(int i = 1; i < vec.size(); i++)
      |                      ~~^~~~~~~~~~~~

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