Submission #1044118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044118		vjudge1	Zagonetka (COI18_zagonetka)	C++17	0 / 100	19 ms	444 KiB

zagonetka

#include<bits/stdc++.h>

using namespace std;

void print(vector<int> v)
{
  for(int i = 0; i + 1 < v.size(); i++)
    cout << v[i] << ' ';
  cout << v.back() << endl;
}

bool ask(vector<int> v)
{
  cout << "query ";
  print(v); 
  bool res;
  cin >> res;
  return res;
}

void out(vector<int> a, vector<int> b)
{
  cout << "end\n";
  print(a);
  print(b);
  exit(0);
}

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

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

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

  while(st.size())
    {
      int u = *st.begin();
      //cerr << u << endl;
      u *= m;
      st.erase(st.begin());
      topo.push_back(u);

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

  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;
  bool f[n] = {};
  for(int v = 1; v <= n && conditions.empty(); v++)
    {
      vector<int> vec = {idx[v]};
      for(int u = v - 1; u > 0 && conditions.empty(); u--)
	{

	  vector<int> q = p;
	  
	  vec.push_back(idx[u]);
	  for(int j = 0; j + 1 < vec.size(); j++)
	    swap(q[vec[j]], q[vec[j + 1]]);

	  int cur = vec.back();
	  while(G[cur].size())
	    {
	      // cerr << "cur = " << cur << endl;
	      int i = G[cur][0];
	      for(int k : G[cur])
		if(q[i] < q[k])
		  i = k;
	      swap(q[i], q[cur]);
	      cur = i;
	    }
	  
	  bool res = ask(q);
	  
	  if(!res)
	    {
	      conditions.push_back({vec.back(), vec[0]});
	      G[vec.back()].push_back(vec[0]);
	      I[vec[0]].push_back(vec.back());
	      // cerr << vec[0] << ' ' << vec.back() << endl;
	    }
	  vec.pop_back();
	}  
    }
  /*
    for(auto [x, y] : conditions)
    {
    // G[x].push_back(y), I[y].push_back(x);
    cerr << x << ' ' << y << endl;
    }
    // */
  assert(conditions.size() == 1);
  vector<int> a = compute(G, 1);
  vector<int> b = compute(G, -1);
  out(a, b);
  return 0;
}

Compilation message (stderr)

zagonetka.cpp: In function 'void print(std::vector<int>)':
zagonetka.cpp:7:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |   for(int i = 0; i + 1 < v.size(); i++)
      |                  ~~~~~~^~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:93:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for(int j = 0; j + 1 < vec.size(); j++)
      |                   ~~~~~~^~~~~~~~~~~~
zagonetka.cpp:83:8: warning: unused variable 'f' [-Wunused-variable]
   83 |   bool f[n] = {};
      |        ^

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