ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211432 | #3805. 折纸游戏 | drdilyor | 40 | 1962ms | 48752kb | C++11 | 3.4kb | 2024-08-11 12:41:50 | 2024-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