답안 #105540

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105540 2019-04-13T10:59:11 Z faustaadp Zagonetka (COI18_zagonetka) C++17
9 / 100
75 ms 384 KB
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
using namespace std;
ll n,a[110],tany[110],i,j,b1[110],b2[110],te1,te2,jaw1[110],jaw2[110],d[110][110],inv[110];
vector<ll> v1[110],v2[110];
ll te3,b3[110];
ll tanya()
{
	cout<<"query";
	ll ii;
	for(ii=1;ii<=n;ii++)cout<<" "<<tany[ii];
	cout<<endl;
	ll H=0;
	cin>>H;
	return H;
}
void dfs3(ll aa)
{
	b3[aa]=1;
	ll ii;
	for(ii=0;ii<v1[aa].size();ii++)
		if(!b3[v1[aa][ii]])
			dfs3(v1[aa][ii]);
	tany[aa]=te3;
	te3--;
}
ll depe(ll aa,ll bb)
{
	if(d[aa][bb]!=-1)return d[aa][bb];
	d[aa][bb]=0;
	ll ii,jj;
	if(a[aa]<a[bb])
	{
		depe(inv[a[aa]+1],bb);
		depe(aa,inv[a[bb]-1]);
	}
	for(ii=1;ii<=n;ii++)b3[ii]=0;
	dfs3(aa);
	if(b3[bb])
	{
		if(a[aa]<a[bb])v1[aa].pb(bb);
		else v1[bb].pb(aa);
		if(a[aa]<a[bb])v2[aa].pb(bb);
		else v2[bb].pb(aa);
		d[aa][bb]=1;
		return 1;
	}
	v1[bb].pb(aa);
	te3=n;
	for(ii=1;ii<=n;ii++)b3[ii]=0;
	for(ii=n;ii>=1;ii--)
		if(!b3[inv[ii]])
			dfs3(inv[ii]);
	v1[bb].pop_back();
	//cout<<aa<<" "<<bb<<"\n";
	if(!tanya())
	{
		d[aa][bb]=1;
		if(a[aa]<a[bb])v1[aa].pb(bb);
		else v1[bb].pb(aa);
		if(a[aa]<a[bb])v2[aa].pb(bb);
		else v2[bb].pb(aa);
	}
	else
		d[aa][bb]=0;
	return d[aa][bb];
}
void dfs1(ll aa)
{
	b1[aa]=1;
	ll ii;
	for(ii=0;ii<v1[aa].size();ii++)
		if(!b1[v1[aa][ii]])
			dfs1(v1[aa][ii]);
	jaw1[aa]=te1;
	te1--;
}
void dfs2(ll aa)
{
	b2[aa]=1;
	ll ii;
	for(ii=0;ii<v2[aa].size();ii++)
		if(!b2[v2[aa][ii]])
			dfs2(v2[aa][ii]);
	jaw2[aa]=te2;
	te2--;
}
int main()
{
	//ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n;i++)inv[a[i]]=i;
	memset(d,-1,sizeof(d));
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i]<a[j])
				depe(i,j);
	cout<<"end"<<endl;
	for(i=1;i<=n;i++)sort(v1[i].begin(),v1[i].end());
	for(i=1;i<=n;i++)sort(v2[i].begin(),v2[i].end());
	for(i=1;i<=n;i++)reverse(v1[i].begin(),v1[i].end());
	te1=n;
	for(i=n;i>=1;i--)
		if(!b1[i])
			dfs1(i);
	te2=n;
	for(i=1;i<=n;i++)
		if(!b2[i])
			dfs2(i);
	for(i=1;i<=n;i++)
		if(i<n)cout<<jaw1[i]<<" ";
		else cout<<jaw1[i]<<endl;
	for(i=1;i<=n;i++)
		if(i<n)cout<<jaw2[i]<<" ";
		else cout<<jaw2[i]<<endl;
}

Compilation message

zagonetka.cpp: In function 'void dfs3(ll)':
zagonetka.cpp:25:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v1[aa].size();ii++)
           ~~^~~~~~~~~~~~~~
zagonetka.cpp: In function 'll depe(ll, ll)':
zagonetka.cpp:35:8: warning: unused variable 'jj' [-Wunused-variable]
  ll ii,jj;
        ^~
zagonetka.cpp: In function 'void dfs1(ll)':
zagonetka.cpp:76:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v1[aa].size();ii++)
           ~~^~~~~~~~~~~~~~
zagonetka.cpp: In function 'void dfs2(ll)':
zagonetka.cpp:86:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v2[aa].size();ii++)
           ~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 384 KB Output is correct
2 Incorrect 26 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -