oj.uz

Submission #135367

# Submission time Handle Problem Language Result Execution time Memory
135367 2019-07-24T04:24:45 Z mohammedehab2002 Zagonetka (COI18_zagonetka) C++11
27 / 100
 94 ms 400 KB 
#include <bits/stdc++.h>
using namespace std;
bool vis[105],mat[105][105];
vector<int> v[105],s;
int n,p[105],q[105],inv[105],ans[2][105];
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;
}
void dfs2(int node,int s)
{
	vis[node]=1;
	mat[s][node]=1;
	for (int u:v[node])
	{
		if (!vis[u])
		dfs2(u,s);
	}
}
void solve(int l,int r,vector<int> v,int i)
{
	vector<int> a,b;
	for (int u:v)
	{
		if (u==v[0])
		continue;
		if (i)
		{
			if (mat[v[0]][u])
			a.push_back(u);
			else
			b.push_back(u);
		}
		else
		{
			if (mat[u][v[0]])
			a.push_back(u);
			else
			b.push_back(u);
		}
	}
	if (i)
	{
		ans[i][v[0]]=r-(int)a.size();
		if (!a.empty())
		solve(r-(int)a.size()+1,r,a,i);
		if (!b.empty())
		solve(l,r-(int)a.size()-1,b,i);
	}
	else
	{
		ans[i][v[0]]=l+a.size();
		if (!a.empty())
		solve(l,l+a.size()-1,a,i);
		if (!b.empty())
		solve(l+a.size()+1,r,b,i);
	}
}
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]);
		}
	}
	printf("end\n");
	vector<int> v;
	for (int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		dfs2(i,i);
		v.push_back(i);
	}
	solve(1,n,v,0);
	solve(1,n,v,1);
	for (int i=0;i<2;i++)
	{
		for (int j=1;j<=n;j++)
		printf("%d ",ans[i][j]);
		printf("\n");
	}
	fflush(stdout);
}

Compilation message

zagonetka.cpp: In function 'bool query()':
zagonetka.cpp:24: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:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
zagonetka.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 320 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 320 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 248 KB Output is correct
2 Correct 21 ms 320 KB Output is correct
3 Correct 37 ms 376 KB Output is correct
4 Correct 42 ms 376 KB Output is correct
5 Correct 12 ms 316 KB Output is correct
6 Correct 45 ms 376 KB Output is correct
7 Correct 9 ms 248 KB Output is correct
8 Correct 9 ms 376 KB Output is correct
9 Correct 37 ms 376 KB Output is correct
10 Correct 19 ms 376 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 376 KB Output is correct
2 Correct 94 ms 376 KB Output is correct
3 Correct 66 ms 316 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 248 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Incorrect 9 ms 248 KB Output isn't correct
8 Halted 0 ms 0 KB -