UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211432#3805. 折纸游戏drdilyor401962ms48752kbC++113.4kb2024-08-11 12:41:502024-08-11 13:17:12

answer

#include<bits/stdc++.h>
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
const int mod=998244353;
struct mint{
    int x;mint(int o=0){x=o;}mint&operator+=(mint a){return(x+=a.x)%=mod,*this;}mint&operator-=(mint a){return(x+=mod-a.x)%=mod,*this;}
    mint&operator*=(mint a){return(x=1ll*x*a.x%mod),*this;}mint&operator^=( int b){mint a=*this;x=1;while(b)(b&1)&&(*this*=a,1),a*=a,b>>=1;return*this;}
    mint&operator/=(mint a){return*this*=(a^=mod-2);}friend mint operator+(mint a,mint b){return a+=b;}friend mint operator-(mint a,mint b){return a-=b;}
    friend mint operator*(mint a,mint b){return a*=b;}friend mint operator/(mint a,mint b){return a/=b;}friend mint operator^(mint a,int b){return a^=b;}
    mint operator-(){return 0-*this;}bool operator==(const mint b)const{return x==b.x;}
};
int n,p1,p2;
int mn[5000005];
int head[5000005],nxt[5000005];
void write(int x){
	if(x<10){putchar(x+'0');return;}
	write(x/10);putchar(x%10+'0');
}
signed main(){
	for(int i=2;i<=5000000;i++){
		if(!mn[i]){
			for(int j=i;j<=5000000;j+=i){
				if(!mn[j])mn[j]=i;
			}
		}
	}
	n=read(),p1=read(),p2=read();
	int s=1,t=n;
	for(int i=1;i<=n;i++)head[i]=i;
	while(n>1){
		if(n%2==0){
			if(p1==2){
				for(int i=s,j=t;i<j;i++,j--){
					vector<int>v;
					for(int k=head[j];k;k=nxt[k])v.push_back(k);
					reverse(v.begin(),v.end());
					nxt[v.back()]=head[i];
					head[j]=0;head[i]=v[0];
					for(int k=0;k<(int)v.size()-1;k++)nxt[v[k]]=v[k+1];
				}
				t=(s+t)/2;
			}
			else{
				for(int i=s,j=t;i<j;i++,j--){
					vector<int>v;
					for(int k=head[i];k;k=nxt[k])v.push_back(k);
					reverse(v.begin(),v.end());
					nxt[v.back()]=head[j];
					head[j]=0;head[i]=v[0];
					for(int k=0;k<(int)v.size()-1;k++)nxt[v[k]]=v[k+1];
				}
				t=(s+t)/2;
			}
			n/=2;continue;
		}
		if(!mn[n]){
			if(p2==2){
				vector<int>v;
				for(int k=head[t];k;k=nxt[k])v.push_back(k);
				reverse(v.begin(),v.end());
				nxt[v.back()]=head[t-1];
				for(int k=0;k<(int)v.size()-1;k++)nxt[v[k]]=v[k+1];
				head[t]=0;head[t-1]=v[0];
				t--;
			}
			else{
				vector<int>v;
				for(int k=head[s];k;k=nxt[k])v.push_back(k);
				reverse(v.begin(),v.end());
				nxt[v.back()]=head[s+1];
				for(int k=head[s+1];k;k=nxt[k])v.push_back(k);
				head[s]=0;head[s+1]=v[0];
				s++;
				//nxt[v.back()]=0;
				for(int k=0;k<(int)v.size()-1;k++)nxt[v[k]]=v[k+1];
			}
			n--;continue;
		}
		if(p2==2){
			for(int i=t-n*2/mn[n]+1,j=t;i<j;i++,j--){
				vector<int>v;
				for(int k=head[j];k;k=nxt[k])v.push_back(k);
				reverse(v.begin(),v.end());
				for(int k=0;k<(int)v.size()-1;k++)nxt[v[k]]=v[k+1];
				nxt[v.back()]=head[i];
				head[i]=v[0];head[j]=0;
			}
			t-=n/mn[n];
		}
		else{
			for(int i=s,j=s+n*2/mn[n]-1;i<j;i++,j--){
				vector<int>v;
				for(int k=head[i];k;k=nxt[k])v.push_back(k);
				reverse(v.begin(),v.end());
				nxt[v.back()]=head[j];
				//for(int k=head[j];k;k=nxt[k])v.push_back(k);
				head[i]=0;head[j]=v[0];
				//nxt[v.back()]=0;
				for(int k=0;k<(int)v.size()-1;k++)nxt[v[k]]=v[k+1];
			}
			s+=n/mn[n];
		}
		n-=n/mn[n];
	}
	for(int i=head[s];i;i=nxt[i])write(i),putchar('\n');
	//维护最左边的一列.
	//每列的开头 head, 下一个 nxt.
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 144ms
memory: 20716kb

input:

15 2 2

output:

2
12
9
8
13
3
4
14
7
6
15
5
10
11
1

result:

ok 15 tokens

Test #2:

score: 0
Wrong Answer
time: 133ms
memory: 20724kb

input:

33 1 2

output:

16
29
7
4
26
19
18
27
5
6
28
17
22
23
1
12
33
11
10
32
13
14
31
9
2
24
21
20
25
3
8
30
15

result:

wrong answer 1st words differ - expected: '19', found: '16'

Test #3:

score: 10
Accepted
time: 126ms
memory: 20728kb

input:

450 2 1

output:

108
343
408
43
258
193
208
243
58
393
358
93
158
293
8
443
308
143
148
303
448
3
298
153
98
353
398
...

result:

ok 450 tokens

Test #4:

score: 0
Wrong Answer
time: 130ms
memory: 20732kb

input:

667 1 1

output:

456
241
166
531
572
125
282
415
398
299
108
589
630
67
50
9
647
340
357
514
183
224
473
484
213
194
...

result:

wrong answer 1st words differ - expected: '666', found: '456'

Test #5:

score: 10
Accepted
time: 69ms
memory: 20736kb

input:

960 2 2

output:

2
959
482
479
242
719
722
239
122
839
602
359
362
599
842
119
62
899
542
419
302
659
782
179
182
779...

result:

ok 960 tokens

Test #6:

score: 10
Accepted
time: 63ms
memory: 20764kb

input:

3000 2 1

output:

158
2843
1658
1343
908
2093
2408
593
658
2343
2158
843
1408
1593
2908
93
408
2593
1908
1093
1158
184...

result:

ok 3000 tokens

Test #7:

score: 0
Wrong Answer
time: 75ms
memory: 21616kb

input:

78125 1 2

output:

39064
23437
7814
70314
54687
57814
67187
4687
26564
35937
32814
29687
1564
64064
60937
45314
17187
1...

result:

wrong answer 1st words differ - expected: '58593', found: '39064'

Test #8:

score: 0
Wrong Answer
time: 1222ms
memory: 48752kb

input:

2022161 1 1

output:

1284641
802752
1936951
150442
632331
1455062
1545565
541828
240945
1846448
893255
1194138
1154179
93...

result:

wrong answer 1st words differ - expected: '2022160', found: '1284641'

Test #9:

score: 0
Time Limit Exceeded

input:

4194304 1 1


output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

4999999 2 1


output:


result: