Submission #135340

#	Time	Username	Problem	Language	Result	Execution time	Memory
135340		mohammedehab2002	Zagonetka (COI18_zagonetka)	C++11	0 / 100	85 ms	248 KiB

zagonetka

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
bool vis[105];
vector<int> v[105],rev[105],s;
int n,p[105],q[105],inv[105];
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> t;
void dfs(int node)
{
	vis[node]=1;
	for (int u:v[node])
	{
		if (!vis[u])
		dfs(u);
	}
	s.push_back(node);
}
bool query()
{
	printf("query");
	for (int i=1;i<=n;i++)
	printf(" %d",q[i]);
	printf("\n");
	fflush(stdout);
	int ans;
	scanf("%d",&ans);
	return ans;
}
int dfs2(int node,int s)
{
	vis[node]=1;
	int ans=(node>s);
	for (int u:rev[node])
	{
		if (!vis[u])
		ans+=dfs2(u,s);
	}
	return ans;
}
int dfs3(int node,int s)
{
	vis[node]=1;
	int ans=(node>=s);
	for (int u:v[node])
	{
		if (!vis[u])
		ans+=dfs3(u,s);
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		inv[p[i]]=i;
	}
	for (int len=1;len<n;len++)
	{
		for (int l=1;l+len<=n;l++)
		{
			int r=l+len;
			memset(vis,0,sizeof(vis));
			s.clear();
			dfs(inv[l]);
			if (vis[inv[r]])
			break;
			dfs(inv[r]);
			for (int j=1;j<=n;j++)
			{
				q[j]=p[j];
				if (!vis[j])
				dfs(j);
			}
			int cur=l;
			reverse(s.begin(),s.end());
			for (int j:s)
			{
				if (l<=p[j] && p[j]<=r)
				q[j]=cur++;
			}
			if (!query())
			{
				v[inv[l]].push_back(inv[r]);
				rev[inv[r]].push_back(inv[l]);
			}
		}
	}
	printf("end\n");
	for (int i=1;i<=n;i++)
	t.insert(i);
	for (int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		auto it=t.find_by_order(dfs2(i,i));
		printf("%d ",*it);
		t.erase(it);
	}
	printf("\n");
	for (int i=1;i<=n;i++)
	t.insert(i);
	for (int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		auto it=t.find_by_order(t.size()-dfs3(i,i));
		printf("%d ",*it);
		t.erase(it);
	}
	printf("\n");
	fflush(stdout);
}

Compilation message (stderr)

zagonetka.cpp: In function 'bool query()':
zagonetka.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&ans);
  ~~~~~^~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
zagonetka.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p[i]);
   ~~~~~^~~~~~~~~~~~

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