QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#443732#8523. Puzzle IIucup-team3890#TL 1ms5616kbC++141.8kb2024-06-15 16:24:022024-06-15 16:24:02

Judging History

This is the latest submission verdict.

  • [2024-06-15 16:24:02]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 5616kb
  • [2024-06-15 16:24:02]
  • Submitted

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

output:


result: