QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#589329#7535. Limited Shuffle RestoringKevin5307RE 0ms0kbC++202.8kb2024-09-25 17:11:482024-09-25 17:11:48

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 17:11:48]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

result: