QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #460905 | #8523. Puzzle II | ucup-team052# | RE | 243ms | 10528kb | C++23 | 6.0kb | 2024-07-02 13:02:45 | 2024-07-02 13:02:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
mt19937 rnd(1);
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 300005
char s[2][N];
int n,k;
struct Treap
{
int ch[N][2],val[N],siz[N],sum[N],key[N];
void pushup(int u)
{
siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;
sum[u]=sum[ch[u][0]]+sum[ch[u][1]]+val[u];
}
int merge(int u,int v)
{
if(!u||!v) return u|v;
if(key[u]<key[v])
{
ch[u][1]=merge(ch[u][1],v);
pushup(u); return u;
}
else
{
ch[v][0]=merge(u,ch[v][0]);
pushup(v); return v;
}
}
pair<int,int> split(int u,int size)
{
if(!u) return {0,0};
assert(siz[u]>=size);
// printf("%d %d %d - %d %d\n",u,ch[u][0],ch[u][1],siz[u],size);
if(siz[ch[u][0]]>=size)
{
auto [A,B]=split(ch[u][0],size);
ch[u][0]=B;
pushup(u);
// printf("* %d %d\n",A,u);
return {A,u};
}
else
{
auto [A,B]=split(ch[u][1],size-1-siz[ch[u][0]]);
ch[u][1]=A;
pushup(u);
return {u,B};
}
}
int find0(int rt) // return index from left
{
int cur=rt;
if(sum[cur]==siz[cur]) return -1;
int prew=0;
while(1)
{
if(ch[cur][0]&&siz[ch[cur][0]]!=sum[ch[cur][0]]) cur=ch[cur][0];
else if(val[cur]==0) return prew+siz[ch[cur][0]]+1;
else prew+=siz[ch[cur][0]]+1,cur=ch[cur][1];
}
}
int find0(int rt,int suf) // return index from left
{
auto [L,R]=split(rt,suf);
int tw=find0(R);
if(tw!=-1)
{
merge(L,R);
return tw+suf;
}
else
{
merge(L,R);
return find0(rt);
}
}
int find1(int rt)
{
int cur=rt;
if(sum[cur]==0) return -1;
int prew=0;
while(1)
{
if(ch[cur][0]&&0!=sum[ch[cur][0]]) cur=ch[cur][0];
else if(val[cur]==1) return prew+siz[ch[cur][0]]+1;
else prew+=siz[ch[cur][0]]+1,cur=ch[cur][1];
}
}
int find1(int rt,int suf)
{
auto [L,R]=split(rt,suf);
int tw=find1(R);
if(tw!=-1)
{
merge(L,R);
return tw+suf;
}
else
{
merge(L,R);
return find1(rt);
}
}
int qval(int rt,int rk)
{
int cur=rt;
while(1)
{
if(rk==siz[ch[cur][0]]+1) return val[cur];
else if(rk<=siz[ch[cur][0]]) cur=ch[cur][0];
else rk-=siz[ch[cur][0]]+1,cur=ch[cur][1];
}
}
void print(int rt)
{
if(!rt) return ;
print(ch[rt][0]);
printf("%d : %d %d - %d %d\n",rt,ch[rt][0],ch[rt][1],sum[rt],siz[rt]);
print(ch[rt][1]);
}
}tr;
int rta,rtb;
vector<pair<int,int>> ans;
/*
void doit(int x,int y)
{
ans.emplace_back(x,y);
if(x+k-1<=n&&y+k-1<=n)
{
int la,ma,ra;
tie(la,ma)=tr.split(rta,x-1);
tie(ma,ra)=tr.split(ma,k);
int lb,mb,rb;
tie(lb,mb)=tr.split(rtb,y-1);
tie(mb,rb)=tr.split(mb,k);
rta=tr.merge(tr.merge(la,mb),ra);
rtb=tr.merge(tr.merge(lb,ma),rb);
}
else if(x+k-1<=n&&y+k-1>n)
{
int la,ma,ra;
tie(la,ma)=tr.split(rta,x-1);
tie(ma,ra)=tr.split(ma,k);
int lb,mb,rb;
tie(lb,mb)=tr.split(rtb,y+k-1-n);
tie(mb,rb)=tr.split(mb,n-k);
int tmp=tr.merge(rb,lb);
rta=tr.merge(tr.merge(la,tmp),ra);
auto [L,R]=tr.split(ma,n-y+1);
rtb=tr.merge(tr.merge(R,mb),L);
}
else if(x+k-1>n&&y+k-1<=n)
{
int lb,mb,rb;
tie(lb,mb)=tr.split(rtb,y-1);
tie(mb,rb)=tr.split(mb,k);
int la,ma,ra;
tie(la,ma)=tr.split(rta,x+k-1-n);
tie(ma,ra)=tr.split(ma,n-k);
int tmp=tr.merge(ra,la);
rtb=tr.merge(tr.merge(lb,tmp),rb);
auto [L,R]=tr.split(mb,n-x+1);
rta=tr.merge(tr.merge(R,ma),L);
}
else
{
int la,ma,ra;
tie(la,ma)=tr.split(rta,x+k-1-n);
tie(ma,ra)=tr.split(ma,n-k);
int lb,mb,rb;
tie(lb,mb)=tr.split(rtb,y+k-1-n);
tie(mb,rb)=tr.split(mb,n-k);
int ta=tr.merge(ra,la),tb=tr.merge(rb,lb);
auto [L,R]=tr.split(tb,n-x+1);
rta=tr.merge(tr.merge(R,ma),L);
tie(L,R)=tr.split(ta,n-y+1);
rtb=tr.merge(tr.merge(R,mb),L);
}
}
*/
void doit(int x,int y)
{
ans.emplace_back(x,y);
{
auto [L,R]=tr.split(rta,x-1);
rta=tr.merge(R,L);
tie(L,R)=tr.split(rtb,y-1);
rtb=tr.merge(R,L);
}
auto [la,ra]=tr.split(rta,k);
auto [lb,rb]=tr.split(rtb,k);
rta=tr.merge(lb,ra);
rtb=tr.merge(la,rb);
// tr.print(rta),tr.print(rtb);
// exit(0);
{
auto [L,R]=tr.split(rta,n-x+1);
rta=tr.merge(R,L);
tie(L,R)=tr.split(rtb,n-y+1);
rtb=tr.merge(R,L);
}
}
int norm(int x)
{
while(x>n) x-=n;
while(x<1) x+=n;
return x;
}
signed main()
{
cin>>n>>k;
scanf("%s%s",s[0]+1,s[1]+1);
for(int i=1;i<=n;i++)
{
if(s[0][i]=='B') tr.val[i]=0;
else tr.val[i]=1;
if(s[1][i]=='B') tr.val[i+n]=0;
else tr.val[i+n]=1;
tr.key[i]=rnd(),tr.key[i+n]=rnd();
tr.pushup(i),tr.pushup(i+n);
}
rta=1,rtb=n+1;
for(int i=2;i<=n;i++) rta=tr.merge(rta,i);
for(int i=2;i<=n;i++) rtb=tr.merge(rtb,i+n);
// return 0;
// tr.print(rta),tr.print(rtb);
int lsta=0,lstb=0;
for(int i=1;i<=n-k;i++)
{
int ida=tr.find1(rta,lsta);
int idb=tr.find0(rtb,lstb);
lsta=ida,lstb=idb;
if(ida==-1) break;
// printf("%d %d\n",ida,idb);
// if(i==3) return 0;
doit(ida,idb);
}
// tr.print(rta),tr.print(rtb);
// return 0;
{
int sum1=0;
for(int i=1;i<=n;i++) sum1+=tr.qval(rtb,i);
if(sum1-(n-k)<(k+1)/2)
{
int ida=tr.find1(rta,lsta);
int idb=tr.find0(rtb,lstb);
lsta=ida,lstb=idb;
doit(ida,idb);
}
}
while(1)
{
int ida=tr.find1(rta);
int idb=tr.find0(rtb);
if(ida==-1) break;
doit(norm(ida+1),norm(idb-k+1));
doit(ida,norm(idb-k+1));
}
cout<<ans.size()<<endl;
for(auto [x,y]:ans) printf("%d %d\n",x,y);
// for(int i=1;i<=n;i++) printf("%d%c",tr.qval(rta,i)," \n"[i==n]);
// for(int i=1;i<=n;i++) printf("%d%c",tr.qval(rtb,i)," \n"[i==n]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7972kb
input:
6 3 BCCBCC BBCBBC
output:
2 2 1 4 3
result:
ok moves = 2
Test #2:
score: 0
Accepted
time: 1ms
memory: 8004kb
input:
2 1 BC BC
output:
1 2 1
result:
ok moves = 1
Test #3:
score: 0
Accepted
time: 1ms
memory: 7784kb
input:
2 1 BB CC
output:
0
result:
ok moves = 0
Test #4:
score: 0
Accepted
time: 1ms
memory: 8048kb
input:
2 1 CC BB
output:
2 1 1 2 2
result:
ok moves = 2
Test #5:
score: 0
Accepted
time: 1ms
memory: 7976kb
input:
3 1 CCC BBB
output:
3 1 1 2 2 3 3
result:
ok moves = 3
Test #6:
score: 0
Accepted
time: 1ms
memory: 8060kb
input:
3 1 CBC BCB
output:
2 1 1 3 3
result:
ok moves = 2
Test #7:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
3 2 BBB CCC
output:
0
result:
ok moves = 0
Test #8:
score: 0
Accepted
time: 1ms
memory: 7928kb
input:
3 2 BCB BCC
output:
3 2 1 1 1 3 1
result:
ok moves = 3
Test #9:
score: 0
Accepted
time: 1ms
memory: 8060kb
input:
4 2 CCCB BBCB
output:
4 1 1 3 4 1 4 4 4
result:
ok moves = 4
Test #10:
score: 0
Accepted
time: 0ms
memory: 7984kb
input:
9 6 CCCBCCCBB BBBCBBBCC
output:
7 1 1 4 4 5 5 2 5 1 5 7 3 6 3
result:
ok moves = 7
Test #11:
score: 0
Accepted
time: 0ms
memory: 8068kb
input:
21 3 CCCCBBCBCCCCCCCBCCCCC BBCCBCBBBBBBBBBCBBBBB
output:
20 1 1 3 5 4 7 7 8 10 9 11 12 14 13 15 15 16 16 17 17 18 18 19 19 20 20 21 21 2 2 3 3 5 5 6 6 9 6 8 6
result:
ok moves = 20
Test #12:
score: 0
Accepted
time: 0ms
memory: 8100kb
input:
49 41 CBCCBCCBCCBCCBCCCBBCCBCBBCCCBBCCBCBCBCBCCCCBCBCCB BCCCCBCBBBBCBCBBBBBCBBBBCCCCBCBBCBBCBBBBCBCBCBBBC
output:
43 1 1 2 2 3 6 4 8 5 9 9 11 10 12 11 14 12 15 2 12 1 12 3 15 2 15 16 10 15 10 20 10 19 10 20 30 19 30 20 10 19 10 20 35 19 35 21 36 20 36 23 10 22 10 25 40 24 40 29 10 28 10 29 44 28 44 29 10 28 10 30 46 29 46 34 10 33 10 35 5 34 5 35 8 34 8
result:
ok moves = 43
Test #13:
score: 0
Accepted
time: 1ms
memory: 7920kb
input:
114 8 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
output:
0
result:
ok moves = 0
Test #14:
score: 0
Accepted
time: 1ms
memory: 8056kb
input:
266 28 CBBCBBCCCCBCBBCBBBCBCBCBCBBCBCBBCCCCBCCCCCBCCBBCCBBCBCBBCCCCCCBBBCCCBCCBCBBCCCBCCCCCCBCBBCCCBCBBCCBCBBBCBCCCBBCBCCCCBBCBBCBBCCBBCCCCCBBCCCBCCCCCCCCBBBBBBCBCCBCCCCBBCBBBBCBCCCCCCCBCBBCBCCCCCCCCCCCBBBBCCCCBCBCCCBCCCCCCCCCBCBCCCBBBCCCBCCBCBBCBCCCCCCBCBCCCCBCBCCBCCCCBCB CCBCBCBBCBCBBCBCCCBBBCBCBB...
output:
262 1 3 2 4 4 5 5 6 7 7 9 11 10 12 11 13 13 14 15 15 18 16 19 17 20 20 23 21 24 22 25 23 26 24 28 25 30 26 37 27 38 29 39 30 40 34 45 37 51 39 52 41 54 45 56 47 58 52 62 53 67 54 69 55 71 58 72 60 75 62 76 63 78 65 81 68 83 72 84 74 85 75 86 82 87 83 89 88 90 89 96 90 98 91 100 93 103 94 107 95 109 ...
result:
ok moves = 262
Test #15:
score: 0
Accepted
time: 1ms
memory: 8000kb
input:
620 443 BBBBBBCBBBCBBCBCBCBBBBCCCBCCBCBBBBBBCCCBBBCCBBCBCBCBBCCCCBCBBCBCCCCBBBBBBCCCCCBBBBCCBCBBBBBCBCBBCBCBCCCCBCBBCBBBCBBBCCCBCCCBBBBBCCBBCCBBBCCBCCBCBBCBCCCCCCCCCBCBCBBBCBBCBBCBBBBBBBCCBBBBBBBBBBCBBCBBCBBCCCBBCCBBBBCCCBBBBBBCBBBBBBBBCBBCBCBBBCCBBBBCCBBBCBCBCBBBBBCBBCBBBBCBBBBCCBBBCBBBBBCBBCCCCBCC...
output:
544 7 4 10 5 13 10 14 11 16 12 17 13 18 14 20 15 21 16 22 17 26 18 28 21 29 22 30 24 31 25 33 26 39 27 40 30 43 32 45 34 47 35 50 36 51 37 53 38 54 39 55 40 57 43 60 47 61 48 65 49 67 52 68 53 69 54 70 58 76 59 77 64 81 65 82 67 83 73 84 74 89 77 90 78 91 79 92 80 94 81 97 82 98 83 102 84 103 86 104...
result:
ok moves = 544
Test #16:
score: 0
Accepted
time: 3ms
memory: 8096kb
input:
1446 646 CCCBCCCCCCCBBCCBBCCCCBBCCCBBCCCCCCCCCCCCCCCBCCCCCCCCBBCCBBCCCBCBBBCCCCBBCCCCCCCCCCCBCBCCCBBCCCCBBCBCBCCCCCCCBCCCCCCCBCCBCBBCCCCCCCCCCCCBCCCBCCCCCCBCCCBCCCCCBBCCCBBCCCBBBCCBCCBCCBBBCBCBCCCCBCBCCCBCCCCBBCCCCCCCBCCCCBCCCBBBCCCBCCBBCCCCBCCCBBCBCCCCCBBCCBCCCCCCBCCCCCCCCCCCCCCBCCCCCBCBCCCCBCCCCCB...
output:
1362 1 2 3 5 4 7 12 14 14 16 15 18 17 19 19 23 21 24 22 27 24 28 34 43 35 45 37 53 39 58 48 60 50 61 51 64 52 65 61 66 64 67 69 71 71 73 76 84 77 85 78 86 79 87 87 90 89 91 95 95 97 96 102 97 103 98 104 99 105 100 106 107 107 111 108 118 109 119 112 121 113 122 118 123 120 125 121 137 122 138 125 14...
result:
ok moves = 1362
Test #17:
score: 0
Accepted
time: 4ms
memory: 8160kb
input:
3374 2755 BCBBCBBBCBBBBBBBBBCCBBBBBBBCCBBCBBCBBBBBCBBBBBBBBCBBBBBBBBBBBBCBBBCCBBBBCBBBBBCBBBBBCBBBBCBBBBBBBBBCBBBBBBBBBBBCBBBBBBBCBBBBBBBBBBCCBBBBBBBBBCBBCBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBCBBCBBBBBBBBBBBBBBCCBCBCBCBBBBCBBBCBBBBBBBBCBBCBCBBCBCCBBBBBBBBBBBCCBBBBBBBBBBBBBBBBBCBBBBBBBBBBB...
output:
1756 2 3 3 4 5 18 6 19 9 23 11 24 20 25 21 27 28 30 30 32 32 36 34 37 36 42 37 43 42 45 44 46 52 55 53 56 65 66 66 67 69 77 71 79 75 97 76 98 81 104 82 105 87 108 88 109 92 113 93 114 102 118 103 119 114 121 115 122 122 123 123 124 133 125 134 127 143 129 145 130 147 131 148 132 151 134 153 135 193 ...
result:
ok moves = 1756
Test #18:
score: 0
Accepted
time: 10ms
memory: 8160kb
input:
7872 7827 BCBBCBCBBCCBCBBBCCCBBBBBBBCBBBBCCBCCBCBBBBBBCBBCBBBCCCBBBCCCCBCBBBBCBBCCBBBBCCBBCBBBCBCBBCBCBBCCBBBCCBBBBCCBBCBBBBBBCBBBBBBBBCCBBCCCCBCCCBBCCCBBCBCBBBCBBBBCBBBBCBCBBBCCBBCCCCBBBCBBCCBBBBBBCBBBBCCCBBBCCCBBCCCBBBBBBCCBBBCCCCBBBCBBCBCCBBBCCCCBCBBCCBBBBCCBBBCBBCBBBCBBBCBBBBCCBBBBBCCBCBCBBBBBBB...
output:
5946 2 1 3 2 5 4 6 5 7 6 10 7 12 11 14 13 15 16 17 17 20 18 24 21 31 23 33 24 37 29 38 31 39 34 40 36 41 41 42 42 48 43 49 44 51 46 52 47 55 49 56 52 59 55 64 59 65 63 66 64 70 66 72 67 74 68 75 70 79 71 80 73 82 74 83 75 86 78 87 79 88 82 91 83 93 88 94 89 95 95 97 96 8 49 7 49 11 47 10 47 11 53 10...
result:
ok moves = 5946
Test #19:
score: 0
Accepted
time: 16ms
memory: 8480kb
input:
18368 17997 CBBBBBBBBBBCBBBBBBBBBBBBBBCBBCCBBBBBBBBBBBBBCBCBBBBBBBBCBBBBBCBBBBBBBBBBBBBBCBBBBBBBBBBCBBBCBCBBBBBCBCBBCBBBBBBBBBBBBBCCCBBBBBBCBBBBCBCBBCBBBBBCBBBBBBBCCBBBBCCBCBBBBBBBBBBBBCBBBBBBBBCBCBBBBBBBBCBCBBBBBBBBBBBCBBBBCCBBBBBBBCBBBBBBBBBBBBBBBCCBBCBCBBCBCBBBCBBBBBBBBBBBBBCBBCBBBBBBBCCCBBBBBBBB...
output:
7654 1 2 2 3 12 10 14 11 28 17 29 18 31 20 32 22 45 44 48 45 49 48 50 49 58 63 59 64 64 65 65 66 79 68 80 69 90 84 91 85 94 97 95 98 96 103 97 104 102 107 104 108 105 126 107 127 109 131 110 132 123 135 125 138 131 145 133 146 137 149 138 150 139 157 140 158 142 167 143 168 148 186 149 187 156 195 1...
result:
ok moves = 7654
Test #20:
score: 0
Accepted
time: 81ms
memory: 9068kb
input:
42858 28689 CCCCCCCCCCCCCCCCCCCCBCCCBBCCCBCCCCCCCCCBCCCCCCCBCCCBCCCCCBCCCCCCCCBCCBCCBCCCCCCCCCCCCCCCCCBCCCCCCCCCBCCCCBCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCCCCCCCCCCCCCCCCBBCCCCCCCCCCCCCCBBCCCBCCCCCCCCCCBCCCCCCCBCCCCBCBCCCBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCBCCCBCBCCCCCCCCCCCCCCBCCCCCCCCBCCCCCCCCCCCCCCCCCC...
output:
40309 1 2 2 22 3 23 7 26 9 27 13 30 14 31 17 40 18 41 29 48 30 49 42 52 43 54 46 59 47 60 54 68 55 70 80 72 81 73 83 75 84 76 86 93 87 94 88 103 89 104 100 108 101 109 103 137 104 139 107 156 109 157 128 171 130 172 131 175 132 176 143 186 144 187 165 194 166 195 168 199 169 200 179 201 180 202 200 ...
result:
ok moves = 40309
Test #21:
score: 0
Accepted
time: 243ms
memory: 10528kb
input:
100002 40466 BBBBBBBCCBCBCCBCBBBBCCBBCBBBBBBBBBBCBBBBCBBBBBCBBBBBBBBBCBBBCBBBCCBCBCBBBBBBCBBBBBBBCBBBBBCBBBBCBCBCBBBBBBBBCBBBBBBBBCBCBBBBCBBBBBBBBBBBBBCBCBBCBBBBBBBBBBBCBBBBBBBCBCBCBCBBBBBBBBCBCBBBBBBBBCBBBBBBBBCBCCBBBCCBBCBBCBBBBBBBBBBCBBBCBBBBBBBBBBBBCBBCCBBCBBCBBBBCBBBBCBBBCCBBBCBBBBBBBCBBBBCBBBC...
output:
90706 8 3 9 5 10 8 11 9 12 12 13 14 14 15 16 16 20 19 21 21 23 33 24 34 34 35 38 36 42 37 43 38 48 44 50 45 59 51 61 52 64 57 65 58 68 61 69 63 70 75 71 76 72 77 73 78 79 80 80 81 87 83 88 84 93 87 94 88 98 89 99 90 100 91 101 92 102 96 103 97 111 100 112 101 120 105 122 106 123 114 124 115 128 116 ...
result:
ok moves = 90706
Test #22:
score: -100
Runtime Error
input:
233338 159967 CCBCBBCCCCBBCCCCCCCCBCCCBCCCCBCCBCCCCCCCCCBCBCCBBCBBCCCCBCCCCCCCCCCCCCCCCCCCBCCBCCBBCBCCBBBCCBCCCCBBCCCBCCCCCCCCCCCBCCBCCCCCCCCBCCCBBCBCCCBCCCCCBCCBCCBCCCCCCCBCCCCCBCCBBCCCCCCCBCCCCCCCCBBBCCCCCCCCCCCCBBBCCCBBCCBCBCCCCCCCCCBCCCCBCCCCCCCCBBCCCCBCCCCBCCCBCCCBCCCCCBCCCCCBBCCCBCCCCCCCCCCCCC...