QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#443732 | #8523. Puzzle II | ucup-team3890# | TL | 1ms | 5616kb | C++14 | 1.8kb | 2024-06-15 16:24:02 | 2024-06-15 16:24:02 |
Judging History
answer
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N=3e5+5;
struct Node{
int pre,nxt;
int col;
}s[N*2];
int er(int x){//returns pre[x]
s[s[x].pre].nxt=s[x].nxt;
s[s[x].nxt].pre=s[x].pre;
return s[x].pre;
}
void ins(int x,int y){//在x后加入y
int w=s[x].nxt;
s[x].nxt=y,s[w].pre=y;
s[y].pre=x,s[y].nxt=w;
}
int n,k;
int u[N],d[N];
vector<pair<int,int>> v;
int main(){
int i;
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>k;
char ch;int cnt=0;
for(i=1;i<=n;i++) cin>>ch,u[i]=(ch=='B'),cnt+=(ch=='B');
for(i=1;i<=n;i++) cin>>ch,d[i]=(ch=='B');
if(cnt*2>n) for(i=1;i<=n;i++) u[i]^=1,d[i]^=1,cnt=n-cnt;
int i1=1,i2=2*n,ik1=k+1,ik2=2*n-k,pos1=1,pos2=n-k;
for(i=1;i<=2*n;i++) s[i].pre=i-1,s[i].nxt=i+1;
for(i=1;i<=n;i++) s[i].col=u[i];
for(i=n+1;i<=2*n;i++) s[i].col=d[i-n];
s[1].pre=n,s[n].nxt=1;
s[n+1].pre=2*n,s[2*n].nxt=n+1;
while(cnt--){
while(s[i1].col!=1) i1=s[i1].nxt,ik1=s[ik1].nxt,pos1++;
while(s[i2].col!=0) i2=s[i2].pre,ik2=s[ik2].pre,pos2--;
v.pb(pos1,pos2);
v.pb(pos1,pos2+1);
auto i3=er(i1),i4=er(i2);
ins(s[ik2].pre,i1);
ins(s[ik1].pre,i2);
i1=s[i3].nxt,i2=i4;
ik2=s[ik2].pre;
// int cc=i1;
// for(i=1;i<=n;i++) cerr<<cc<<' ',cc=s[cc].nxt;cerr<<endl;
// cc=i2;
// for(i=1;i<=n;i++) cerr<<cc<<' ',cc=s[cc].nxt;cerr<<endl;
// cerr<<i1<<' '<<i2<<' '<<ik1<<' '<<ik2<<endl;
// cerr<<pos1<<' '<<pos2<<endl;
}
for(auto& p:v){
p.first=(p.first-1+100*n)%n+1;
p.second=(p.second-1+100*n)%n+1;
}
cout<<v.size()<<'\n';
for(auto p:v) cout<<p.first<<' '<<p.second<<'\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5616kb
input:
6 3 BCCBCC BBCBBC
output:
4 1 3 1 4 4 1 4 2
result:
ok moves = 4
Test #2:
score: 0
Accepted
time: 1ms
memory: 5600kb
input:
2 1 BC BC
output:
2 1 1 1 2
result:
ok moves = 2
Test #3:
score: -100
Time Limit Exceeded
input:
2 1 BB CC