oj.uz

Submission #1043988

# Submission time Handle Problem Language Result Execution time Memory
1043988 2024-08-05T05:51:14 Z vjudge1 Zagonetka (COI18_zagonetka) C++17
0 / 100
 41 ms 440 KB 
#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;
  bool f[n] = {};
  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 = 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)
	    {
	      G[vec.back()].push_back(vec[0]);
	      I[vec[0]].push_back(vec.back());
	      // cerr << vec[0] << ' ' << vec.back() << endl;
	    }
	}  
    }

  for(auto [x, y] : conditions)
    {
      G[x].push_back(y), I[y].push_back(x);
      // cerr << x << ' ' << y << endl;
    }

  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

zagonetka.cpp: In function 'int main()':
zagonetka.cpp:85:25: 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 = 0; j + 1 < vec.size(); j++)
      |                   ~~~~~~^~~~~~~~~~~~
zagonetka.cpp:77:8: warning: unused variable 'f' [-Wunused-variable]
   77 |   bool f[n] = {};
      |        ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 440 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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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