QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#589329 | #7535. Limited Shuffle Restoring | Kevin5307 | RE | 0ms | 0kb | C++20 | 2.8kb | 2024-09-25 17:11:48 | 2024-09-25 17:11:48 |
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int a[50050];
int n;
int query(int x,int y)
{
if(x>n||y>n) return x<y;
cout<<"? "<<x<<" "<<y<<endl;
char ch;
cin>>ch;
return ch=='<';
}
vector<vector<int>> order;
map<int,pii> Mp[6];
int dfs(int mask,int cur)
{
if(__builtin_popcount(mask)>(1<<cur)) return 0;
if(!cur) return 1;
if(Mp[cur].find(mask)!=Mp[cur].end()) return ~Mp[cur][mask].first;
for(int a=0;a<5;a++)
for(int b=a+1;b<5;b++)
{
int m1=0,m2=0;
for(int i=0;i<sz(order);i++)
if(mask>>i&1)
{
for(int j=0;j<sz(order[i]);j++)
if(order[i][j]==a)
{
m1|=(1<<i);
break;
}
else if(order[i][j]==b)
{
m2|=(1<<i);
break;
}
}
if(dfs(m1,cur-1)&&dfs(m2,cur-1))
{
Mp[cur][mask]=mp(a,b);
return 1;
}
}
Mp[cur][mask]=mp(-1,-1);
return 0;
}
void init()
{
for(int a=0;a<3;a++)
for(int b=0;b<3;b++)
for(int c=0;c<3;c++)
{
vector<int> tmp={3,4};
tmp.insert(tmp.begin()+a,2);
tmp.insert(tmp.begin()+b,1);
tmp.insert(tmp.begin()+c,0);
}
assert(dfs((1<<sz(order))-1,5));
}
vector<int> get(int mask,int cur,vector<int> ind)
{
if(__builtin_popcount(mask)==1) return order[__lg(mask)];
int a=Mp[cur][mask].first,b=Mp[cur][mask].second;
int ans=query(ind[a],ind[b]);
int m2=0;
for(int i=0;i<sz(order);i++)
if(mask>>i&1)
{
for(int j=0;j<sz(order[i]);j++)
if(order[i][j]==a)
{
if(ans) m2|=(1<<i);
break;
}
else if(order[i][j]==b)
{
if(!ans) m2|=(1<<i);
break;
}
}
return get(m2,cur-1,ind);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
cin>>n;
vector<int> vec;
int m=(n+2)/3*3;
vec.pb(m+2);
vec.pb(m+1);
for(int i=m;i;i-=3)
{
vector<int> ord={i-2,i-1,i,vec.back(),vec[sz(vec)-2]};
vector<int> ord2=get((1<<sz(order))-1,5,ord);
vec.pop_back();
vec.pop_back();
for(int j=4;j>=0;j--)
vec.pb(ord[ord2[j]]);
}
rev(vec);
for(int i=0;i<sz(vec);i++)
a[vec[i]]=i+1;
cout<<"! ";
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 > > > > >
output:
? 4 5 ? 4 5 ? 4 5 ? 4 5 ? 4 5 ? 4 4