#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],L,R;
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)
{
if(!(L<=a[aa]&&a[aa]<=R))return ;
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]);
}
L=a[aa];
R=a[bb];
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=a[bb];
for(ii=1;ii<=n;ii++)b3[ii]=0;
for(ii=1;ii<=n;ii++)tany[ii]=a[ii];
for(ii=a[bb];ii>=a[aa];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:26: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:36:8: warning: unused variable 'jj' [-Wunused-variable]
ll ii,jj;
^~
zagonetka.cpp: In function 'void dfs1(ll)':
zagonetka.cpp:80: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:90:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v2[aa].size();ii++)
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
