QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #71317 | #4273. Good Game | zhouhuanyi | 3 | 199ms | 49128kb | C++14 | 3.6kb | 2023-01-09 17:22:04 | 2023-01-09 17:22:11 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<set>
#define N 2000000
#define inf 1e9
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int num,data;
bool operator < (const reads &t)const
{
return (data!=t.data)?data>t.data:num<t.num;
}
};
reads st[N+1];
set<reads>s;
int n,length,leng,tong[N+1],pv[N+1],nt[N+1],rt[N+1],L[N+1],R[N+1],sc[N+1];
char c[N+1];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int d)
{
for (;x<=length;x+=lowbit(x)) sc[x]+=d;
return;
}
int query(int x)
{
int res=0;
for (;x>=1;x-=lowbit(x)) res+=sc[x];
return res;
}
void del(int x)
{
int s1=pv[x],s2=nt[x];
nt[s1]=s2,pv[s2]=s1;
if (tong[x]==1)
{
s.erase((reads){rt[x],R[rt[x]]-L[rt[x]]+1});
if (L[rt[x]]==x) L[rt[x]]++;
else R[rt[x]]--;
if (L[rt[x]]<=R[rt[x]]) s.insert((reads){rt[x],R[rt[x]]-L[rt[x]]+1});
}
nt[x]=pv[x]=-1;
return;
}
void solve(int x)
{
for (int i=1;i<=(tong[x]>>1);++i) st[++leng]=(reads){query(x-1)+1,2};
if (tong[x]&1) st[leng].data++;
if (pv[x]&&nt[x]!=length+1) add(pv[x],-tong[pv[x]]),add(nt[x],-tong[nt[x]]),add(x,tong[pv[x]]+tong[nt[x]]-tong[x]),tong[x]=tong[pv[x]]+tong[nt[x]],del(pv[x]),del(nt[x]);
else add(x,-tong[x]),del(x);
return;
}
int main()
{
int d,lst=0,cnt0=0,cnt1=0,cnt,rst=0,mid=0,top;
bool op=1;
n=read();
for (int i=1;i<=n;++i) cin>>c[i];
for (int i=1;i<=n;++i)
if (i==n||c[i]!=c[i+1])
tong[++length]=i-lst,lst=i;
for (int i=1;i<=length;++i) add(i,tong[i]);
for (int i=1;i<=length-1;++i) cnt0+=(tong[i]==1&&tong[i+1]>=2),cnt1+=(tong[i]>=2&&tong[i+1]==1);
for (int i=0;i<=length;++i) nt[i]=i+1,pv[i+1]=i;
for (int i=1;i<=length;++i)
{
if ((i==1||tong[i-1]>=2)&&tong[i]==1) lst=i;
rt[i]=lst;
if ((i==length||tong[i+1]>=2)&&tong[i]==1) L[lst]=lst,R[lst]=i,s.insert((reads){lst,R[lst]-L[lst]+1}),op&=(((i-lst+1)<<1)<=(length-(lst!=1)-(i!=length)));
}
if (tong[1]==1&&cnt0==1&&cnt1==1)
{
cnt0=cnt1=0;
for (int i=1;i<=length;++i)
{
if (tong[i]==1) cnt0++;
else break;
}
for (int i=length;i>=1;--i)
{
if (tong[i]==1) cnt1++;
else break;
}
cnt=length-cnt0-cnt1;
if (cnt>=((n+1)>>1)||((length&1)&&op))
{
if (cnt>=((n+1)>>1))
{
for (int i=1;i<=(cnt0<<1);++i) solve(cnt0+1);
for (int i=1;i<=(cnt1<<1);++i) solve(length-cnt1);
for (int i=1;i<=length;++i)
if (nt[i]!=-1)
solve(i);
}
else
{
if (cnt0<cnt1)
{
for (int i=1;i<=cnt1-cnt0;++i) solve(length-cnt1);
}
else
{
for (int i=1;i<=cnt0-cnt1;++i) solve(cnt0+1);
}
cnt=0;
for (int i=1;i<=length;++i)
if (nt[i]!=-1)
cnt++;
for (int i=1;i<=length;++i)
if (nt[i]!=-1)
{
rst++;
if (rst==((cnt+1)>>1)) mid=i;
}
for (int i=1;i<=((cnt+1)>>1);++i) solve(mid);
}
printf("%d\n",leng);
for (int i=1;i<=leng;++i) printf("%d %d\n",st[i].num,st[i].data);
}
else puts("-1");
return 0;
}
if (op)
{
while (!s.empty())
{
auto it=s.begin();
top=(*it).num,d=(*it).data,it++;
if (s.size()==2&&it!=s.end()&&!pv[L[top]]&&(*it).data==d) top=(*it).num;
if (pv[L[top]]!=-1&&pv[pv[L[top]]]&&tong[pv[L[top]]]>=2) solve(pv[L[top]]);
else solve(nt[R[top]]);
}
for (int i=1;i<=length;++i)
if (nt[i]!=-1)
solve(i);
printf("%d\n",leng);
for (int i=1;i<=leng;++i) printf("%d %d\n",st[i].num,st[i].data);
}
else puts("-1");
return 0;
}
详细
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 2ms
memory: 19884kb
input:
9 ABAABBBAA
output:
4 3 2 2 2 2 2 1 3
result:
ok good solution!
Test #2:
score: 0
Accepted
time: 0ms
memory: 19884kb
input:
13 ABABBABABBABA
output:
6 4 2 7 2 3 2 4 2 2 3 1 2
result:
ok good solution!
Test #3:
score: 0
Accepted
time: 3ms
memory: 20048kb
input:
15 AABABAABABAABAB
output:
7 6 2 9 2 5 2 6 2 4 3 1 2 1 2
result:
ok good solution!
Test #4:
score: 0
Accepted
time: 0ms
memory: 20116kb
input:
15 ABAABBBABAABBAB
output:
7 3 2 2 2 2 2 6 2 4 3 1 2 1 2
result:
ok good solution!
Test #5:
score: 0
Accepted
time: 0ms
memory: 19664kb
input:
1 B
output:
-1
result:
ok no solution
Test #6:
score: 0
Accepted
time: 5ms
memory: 15768kb
input:
2 BB
output:
1 1 2
result:
ok good solution!
Test #7:
score: 0
Accepted
time: 5ms
memory: 15804kb
input:
7 AAAABBB
output:
3 1 2 1 2 1 3
result:
ok good solution!
Test #8:
score: 0
Accepted
time: 2ms
memory: 15836kb
input:
11 BBBBBBAAAAA
output:
5 1 2 1 2 1 2 1 2 1 3
result:
ok good solution!
Test #9:
score: 0
Accepted
time: 2ms
memory: 19804kb
input:
2 AB
output:
-1
result:
ok no solution
Test #10:
score: 0
Accepted
time: 2ms
memory: 19636kb
input:
14 BAAAAAAAAAAAAA
output:
-1
result:
ok no solution
Test #11:
score: 0
Accepted
time: 1ms
memory: 19928kb
input:
14 ABBABAABBABBAB
output:
7 2 2 9 2 4 2 6 2 1 2 1 2 1 2
result:
ok good solution!
Test #12:
score: 0
Accepted
time: 3ms
memory: 20052kb
input:
15 BAABABABBABBAAB
output:
6 2 2 6 2 5 2 4 3 3 3 1 3
result:
ok good solution!
Test #13:
score: 0
Accepted
time: 2ms
memory: 19900kb
input:
14 BABBBBBBBBBBAB
output:
7 3 2 3 2 3 2 3 2 3 2 2 2 1 2
result:
ok good solution!
Test #14:
score: 0
Accepted
time: 2ms
memory: 20060kb
input:
15 BABAAAAAAAAABAB
output:
7 4 2 4 2 4 2 4 3 3 2 2 2 1 2
result:
ok good solution!
Test #15:
score: 0
Accepted
time: 2ms
memory: 20060kb
input:
14 BBBABAAAAAAABA
output:
6 6 2 6 2 6 3 5 2 1 3 1 2
result:
ok good solution!
Test #16:
score: 0
Accepted
time: 1ms
memory: 20052kb
input:
15 AAAABABAAAAABAB
output:
7 8 2 8 3 7 2 6 2 1 2 1 2 1 2
result:
ok good solution!
Test #17:
score: 0
Accepted
time: 2ms
memory: 20056kb
input:
14 BAAABABAAAABAB
output:
6 2 3 5 2 5 2 4 2 3 2 1 3
result:
ok good solution!
Test #18:
score: 0
Accepted
time: 1ms
memory: 19932kb
input:
15 ABAAAABABBBBABA
output:
7 9 2 9 2 3 2 3 2 4 2 2 3 1 2
result:
ok good solution!
Test #19:
score: 0
Accepted
time: 3ms
memory: 17840kb
input:
14 BABAAABAAAABAB
output:
6 4 3 5 2 5 2 3 3 2 2 1 2
result:
ok good solution!
Test #20:
score: 0
Accepted
time: 2ms
memory: 19884kb
input:
15 BABBABABBBBBBAB
output:
7 3 2 2 2 4 2 4 2 4 2 3 2 1 3
result:
ok good solution!
Test #21:
score: 0
Accepted
time: 1ms
memory: 20060kb
input:
14 BABAAAABABBBAB
output:
6 4 2 4 2 3 2 4 3 2 3 1 2
result:
ok good solution!
Test #22:
score: 0
Accepted
time: 1ms
memory: 19852kb
input:
15 BABAAAAAABABAAB
output:
7 4 2 4 2 4 2 3 2 2 2 3 2 1 3
result:
ok good solution!
Test #23:
score: 0
Accepted
time: 2ms
memory: 19884kb
input:
14 BABBBBBABAAAAA
output:
6 3 2 3 3 2 2 1 2 1 2 1 3
result:
ok good solution!
Test #24:
score: 0
Accepted
time: 3ms
memory: 19892kb
input:
15 BABAAAABABAAAAA
output:
7 4 2 4 2 3 2 2 2 1 2 1 2 1 3
result:
ok good solution!
Test #25:
score: 0
Accepted
time: 2ms
memory: 19776kb
input:
15 BAABABAABAABBAA
output:
7 2 2 5 2 4 2 1 2 1 3 1 2 1 2
result:
ok good solution!
Test #26:
score: 0
Accepted
time: 2ms
memory: 19780kb
input:
15 AABAABBAABAABAB
output:
7 11 2 10 2 4 2 6 3 1 2 1 2 1 2
result:
ok good solution!
Test #27:
score: 0
Accepted
time: 0ms
memory: 19924kb
input:
15 AABABBABAABBABB
output:
7 5 2 4 2 7 2 1 2 1 2 1 3 1 2
result:
ok good solution!
Test #28:
score: 0
Accepted
time: 0ms
memory: 19916kb
input:
15 BAABBABBAABABBA
output:
6 9 2 2 2 5 3 6 2 1 3 1 3
result:
ok good solution!
Test #29:
score: 0
Accepted
time: 3ms
memory: 19856kb
input:
15 BBAABBABABABBAA
output:
-1
result:
ok no solution
Test #30:
score: 0
Accepted
time: 6ms
memory: 19856kb
input:
15 ABABBAABBAABBAB
output:
-1
result:
ok no solution
Test #31:
score: 0
Accepted
time: 0ms
memory: 19768kb
input:
14 AAABAAAAABAAAB
output:
5 5 2 5 3 6 3 1 3 1 3
result:
ok good solution!
Test #32:
score: 0
Accepted
time: 1ms
memory: 20060kb
input:
15 ABBBBABBBBBABBB
output:
6 2 2 2 2 3 2 3 3 1 3 1 3
result:
ok good solution!
Test #33:
score: 0
Accepted
time: 0ms
memory: 17840kb
input:
14 BBBBABBABAAABA
output:
6 6 2 8 3 7 2 1 2 1 2 1 3
result:
ok good solution!
Test #34:
score: 0
Accepted
time: 2ms
memory: 20056kb
input:
15 AAAAABABBBABBAB
output:
6 8 3 9 2 7 3 1 2 1 3 1 2
result:
ok good solution!
Test #35:
score: 0
Accepted
time: 6ms
memory: 19888kb
input:
14 AABABBBBABAAAB
output:
6 5 2 5 2 4 2 5 3 1 2 1 3
result:
ok good solution!
Test #36:
score: 0
Accepted
time: 2ms
memory: 19880kb
input:
15 BAABAAAABABBBBA
output:
7 5 2 5 2 2 2 5 2 5 2 1 3 1 2
result:
ok good solution!
Test #37:
score: 0
Accepted
time: 6ms
memory: 19892kb
input:
14 ABBBABAAABAAAB
output:
5 2 3 4 3 5 3 1 2 1 3
result:
ok good solution!
Test #38:
score: 0
Accepted
time: 2ms
memory: 20060kb
input:
15 BAAABABBBBABAAA
output:
6 2 3 4 2 4 2 3 2 1 3 1 3
result:
ok good solution!
Test #39:
score: 0
Accepted
time: 6ms
memory: 19888kb
input:
14 BABBABBBBABAAA
output:
6 3 2 4 2 4 2 2 3 1 2 1 3
result:
ok good solution!
Test #40:
score: 0
Accepted
time: 2ms
memory: 19884kb
input:
15 ABAAABABBBABBBB
output:
6 3 3 2 2 3 3 1 3 1 2 1 2
result:
ok good solution!
Test #41:
score: 0
Accepted
time: 0ms
memory: 19736kb
input:
14 AABABABBAABBAA
output:
-1
result:
ok no solution
Test #42:
score: 0
Accepted
time: 2ms
memory: 19864kb
input:
15 AABBBABABAABBAA
output:
-1
result:
ok no solution
Test #43:
score: 0
Accepted
time: 0ms
memory: 19732kb
input:
14 AABBAABABABBAA
output:
-1
result:
ok no solution
Test #44:
score: 0
Accepted
time: 2ms
memory: 19732kb
input:
15 BBBAABBAABABABB
output:
-1
result:
ok no solution
Test #45:
score: 0
Accepted
time: 1ms
memory: 19868kb
input:
15 BABABBBBAABBAAA
output:
-1
result:
ok no solution
Test #46:
score: 0
Accepted
time: 2ms
memory: 19696kb
input:
15 BBBABABAABBBAAA
output:
-1
result:
ok no solution
Test #47:
score: 0
Accepted
time: 0ms
memory: 19660kb
input:
15 AAABBBBAABABABB
output:
-1
result:
ok no solution
Test #48:
score: 0
Accepted
time: 2ms
memory: 19800kb
input:
15 AAAAABBAABBABAB
output:
-1
result:
ok no solution
Test #49:
score: 0
Accepted
time: 2ms
memory: 19860kb
input:
15 BAAAABBAABBBABA
output:
-1
result:
ok no solution
Test #50:
score: 0
Accepted
time: 3ms
memory: 19856kb
input:
15 BABAAABBBAAABBA
output:
-1
result:
ok no solution
Subtask #2:
score: 0
Time Limit Exceeded
Test #51:
score: 6
Accepted
time: 3ms
memory: 19664kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
-1
result:
ok no solution
Test #52:
score: 0
Accepted
time: 3ms
memory: 19868kb
input:
300 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...
output:
-1
result:
ok no solution
Test #53:
score: 0
Accepted
time: 3ms
memory: 19888kb
input:
299 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
149 96 2 96 2 96 2 96 2 191 2 191 2 191 2 95 2 188 2 94 2 185 2 93 2 182 2 92 2 179 2 91 2 176 2 90 2 173 2 89 2 170 2 88 2 167 2 87 2 164 2 86 2 161 2 85 2 158 2 84 2 155 2 83 2 152 2 82 2 149 2 81 2 146 2 80 2 143 2 79 2 140 2 78 2 137 2 77 2 134 2 76 2 131 2 75 2 128 2 74 2 125 2 73 2 122 2 72 2 ...
result:
ok good solution!
Test #54:
score: 0
Accepted
time: 3ms
memory: 19920kb
input:
299 BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
148 102 3 197 2 197 3 101 2 194 2 100 2 191 2 99 2 188 2 98 2 185 2 97 2 182 2 96 2 179 2 95 2 176 2 94 2 173 2 93 2 170 2 92 2 167 2 91 2 164 2 90 2 161 2 89 2 158 2 88 2 155 2 87 2 152 2 86 2 149 2 85 2 146 2 84 2 143 2 83 2 140 2 82 2 137 2 81 2 134 2 80 2 131 2 79 2 128 2 78 2 125 2 77 2 122 2 7...
result:
ok good solution!
Test #55:
score: -6
Time Limit Exceeded
input:
297 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #102:
score: 7
Accepted
time: 7ms
memory: 19776kb
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 1996 2 1996 2 3991 2 3991 2 3991 2 3991 3 1995 2 3988 2 1994 2 3985 2 1993 2 3982 2 1992 2 3979 2 1991 2 3976 2 1990 2 3973 2 1989 2 3970 2 1988 2 3967 2 1987 2 3964 2 1986 2 3961 2 1985 2 3958 2 1984 2 3955 2 1983 2 3952 2 1982 2 3949 2 1981 2 3946 2 1980 2 3943 2 1979 2 3940 2 1978 2 3937 2 1...
result:
ok good solution!
Test #103:
score: 0
Accepted
time: 1ms
memory: 20052kb
input:
5999 BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 2001 2 2001 2 3996 2 3996 3 2000 2 3993 2 1999 2 3990 2 1998 2 3987 2 1997 2 3984 2 1996 2 3981 2 1995 2 3978 2 1994 2 3975 2 1993 2 3972 2 1992 2 3969 2 1991 2 3966 2 1990 2 3963 2 1989 2 3960 2 1988 2 3957 2 1987 2 3954 2 1986 2 3951 2 1985 2 3948 2 1984 2 3945 2 1983 2 3942 2 1982 2 3939 2 1...
result:
ok good solution!
Test #104:
score: -7
Time Limit Exceeded
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #153:
score: 9
Accepted
time: 199ms
memory: 49128kb
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 333328 2 333328 2 333328 2 666655 2 666655 2 666655 2 666655 2 666655 2 333327 2 666652 2 333326 2 666649 2 333325 2 666646 2 333324 2 666643 2 333323 2 666640 2 333322 2 666637 2 333321 2 666634 2 333320 2 666631 2 333319 2 666628 2 333318 2 666625 2 333317 2 666622 2 333316 2 666619 2 33331...
result:
ok good solution!
Test #154:
score: 0
Accepted
time: 190ms
memory: 49072kb
input:
999998 BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 333334 2 333334 2 333334 2 666661 2 666661 3 333333 2 666658 2 333332 2 666655 2 333331 2 666652 2 333330 2 666649 2 333329 2 666646 2 333328 2 666643 2 333327 2 666640 2 333326 2 666637 2 333325 2 666634 2 333324 2 666631 2 333323 2 666628 2 333322 2 666625 2 333321 2 666622 2 333320 2 66661...
result:
ok good solution!
Test #155:
score: -9
Time Limit Exceeded
input:
999997 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...