QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134199 | #4273. Good Game | blackyuki | 0 | 33ms | 3956kb | C++14 | 4.7kb | 2023-08-03 13:11:46 | 2023-08-03 13:12:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define pb emplace_back
#define lb(v,k) (ll)(lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (ll)(upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define popcnt __builtin_popcountll
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=998244353;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b){if(a>=inf-10)out(b);else out(a);}
vp res;
void f(ll a,ll d){
while(d>0){
ll t=2;
if(d==3)t=3;
res.pb(a,t);
d-=t;
}
}
vp f1(ll n,vi v){
res=vp(0);
ll mid=n/2,pre=0;
rep(i,mid)pre+=v[i];
rep(i,mid+1){
if(i==0)f(pre+1,v[mid]);
else{
pre-=v[mid-i];
f(pre+1,v[mid-i]+v[mid+i]);
}
}
return res;
}
vp f2(ll n,vi v,ll a,ll b){
if(a==0)return f1(n,v);
res=vp(0);
ll mid=n/2,pre=0;
rep(i,mid+b)pre+=v[i];
rep(i,a){
if(i==0)f(pre+1,v[mid+b]);
else{
pre-=v[mid+b-i];
f(pre+1,v[mid+b-i]+v[mid+b+i]);
}
}
vi nv;
rep(i,mid+b-a)nv.pb(v[i]);
nv.pb(v[mid+b-a]+v[mid+b+a]);
REP(i,mid+b+a+1,n)nv.pb(v[i]);
vp ans1=res;
vp ans2=f1(nv.size(),nv);
for(auto x:ans2)ans1.pb(x);
return ans1;
}
vp sol(ll n,string s){
vi v={1};
vp res;
REP(i,1,n){
if(s[i]!=s[i-1])v.pb(0);
v.back()++;
}
n=v.size();
if(n%2){
ll mid=n/2;
if(v[mid]>1)return f1(n,v);
ll a=0,b=0;
while(a<=n/2&&v[mid-a]==1)a++;
while(b<=n/2&&v[mid+b]==1)b++;
if(a+b>n/2)return res;
return f2(n,v,a,b);
}
else{
vi idx;
rep(i,n)if(v[i]>1)idx.pb(i);
ll a=-1,b=0,c=-1,d=0;
for(ll i=1;i<n;i+=2){
while(a+1<idx.size()&&idx[a+1]<=i/2)a++;
while(b<idx.size()&&idx[b]<i/2)b++;
while(c+1<idx.size()&&idx[c+1]<=(n+i)/2)c++;
while(d<idx.size()&&idx[d]<(n+i)/2)d++;
if(a==-1||d==idx.size())continue;
a=i/2-idx[a];b=idx[b]-i/2;
c=(n+i)/2-idx[c];d=idx[d]-(n+i)/2;
if(a+b<=i/2&&c+d<=(n-i)/2){
vi v1,v2;
rep(j,i)v1.pb(v[j]);
REP(j,i,n)v2.pb(v[j]);
vp res1=f2(i,v1,a,b),res2=f2(n-i,v2,c,d);
for(auto x:res2)res1.pb(x);
return res1;
}
}
return res;
}
}
void check(string s,vp ans){
if(ans.size()==0)return;
else{
for(auto x:ans){
ll a=x.fi-1,d=x.se;
REP(i,a,a+d)assert(i<s.size()&&s[i]==s[a]);
assert(d==2||d==3);
string ns;
rep(i,s.size())if(i<a||i>=a+d)ns+=s[i];
s=ns;
}
assert(s=="");
}
}
int main(){
ll n;cin>>n;
string s;cin>>s;
vp ans=sol(n,s);
check(s,ans);
if(ans.size())out(ans.size());
else out(-1);
for(auto x:ans)cout<<x.fi<<' '<<x.se<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 3
Accepted
time: 1ms
memory: 3472kb
input:
9 ABAABBBAA
output:
4 3 2 2 2 2 2 1 3
result:
ok good solution!
Test #2:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
13 ABABBABABBABA
output:
6 9 2 8 2 4 2 3 2 2 3 1 2
result:
ok good solution!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
15 AABABAABABAABAB
output:
7 1 2 9 2 8 2 4 2 3 2 2 3 1 2
result:
ok good solution!
Test #4:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
15 ABAABBBABAABBAB
output:
7 3 2 2 2 2 2 1 2 4 2 2 3 1 2
result:
ok good solution!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
1 B
output:
-1
result:
ok no solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
2 BB
output:
1 1 2
result:
ok good solution!
Test #7:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
7 AAAABBB
output:
3 1 2 1 2 1 3
result:
ok good solution!
Test #8:
score: 0
Accepted
time: 1ms
memory: 3500kb
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: 0ms
memory: 3520kb
input:
2 AB
output:
-1
result:
ok no solution
Test #10:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
14 BAAAAAAAAAAAAA
output:
-1
result:
ok no solution
Test #11:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
14 ABBABAABBABBAB
output:
7 2 2 1 2 7 2 4 2 2 2 2 2 1 2
result:
ok good solution!
Test #12:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
15 BAABABABBABBAAB
output:
6 8 2 7 2 6 3 5 3 2 2 1 3
result:
ok good solution!
Test #13:
score: 0
Accepted
time: 0ms
memory: 3464kb
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: 1ms
memory: 3500kb
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: 0ms
memory: 3580kb
input:
14 BBBABAAAAAAABA
output:
6 1 3 3 2 3 2 3 3 2 2 1 2
result:
ok good solution!
Test #16:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
15 AAAABABAAAAABAB
output:
7 1 2 1 2 4 2 4 3 3 2 2 2 1 2
result:
ok good solution!
Test #17:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
14 BAAABABAAAABAB
output:
6 8 2 8 2 7 2 6 2 2 3 1 3
result:
ok good solution!
Test #18:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
15 ABAAAABABBBBABA
output:
7 9 2 9 2 8 2 3 2 3 2 2 3 1 2
result:
ok good solution!
Test #19:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
14 BABAAABAAAABAB
output:
6 8 2 8 2 4 3 3 3 2 2 1 2
result:
ok good solution!
Test #20:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
15 BABBABABBBBBBAB
output:
7 8 2 8 2 8 2 7 2 3 2 2 2 1 3
result:
ok good solution!
Test #21:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
14 BABAAAABABBBAB
output:
6 10 3 4 2 4 2 3 2 2 3 1 2
result:
ok good solution!
Test #22:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
15 BABAAAAAABABAAB
output:
7 13 2 4 2 4 2 4 2 3 2 2 2 1 3
result:
ok good solution!
Test #23:
score: 0
Accepted
time: 0ms
memory: 3484kb
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: 1ms
memory: 3544kb
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: 0ms
memory: 3480kb
input:
15 BAABABAABAABBAA
output:
7 2 2 1 2 6 2 3 2 2 2 2 2 1 3
result:
ok good solution!
Test #26:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
15 AABAABBAABAABAB
output:
7 1 2 9 2 6 2 4 2 4 2 2 3 1 2
result:
ok good solution!
Test #27:
score: 0
Accepted
time: 1ms
memory: 3472kb
input:
15 AABABBABAABBABB
output:
6 1 2 7 2 6 3 3 2 2 3 1 3
result:
ok good solution!
Test #28:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
15 BAABBABBAABABBA
output:
6 2 2 1 3 8 2 4 2 2 3 1 3
result:
ok good solution!
Test #29:
score: -3
Dangerous Syscalls
input:
15 BBAABBABABABBAA
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #51:
score: 6
Accepted
time: 2ms
memory: 3472kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
-1
result:
ok no solution
Test #52:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
300 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...
output:
-1
result:
ok no solution
Test #53:
score: 0
Accepted
time: 3ms
memory: 3540kb
input:
299 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
149 199 2 199 2 199 2 198 2 197 2 196 2 195 2 194 2 193 2 192 2 191 2 190 2 189 2 188 2 187 2 186 2 185 2 184 2 183 2 182 2 181 2 180 2 179 2 178 2 177 2 176 2 175 2 174 2 173 2 172 2 171 2 170 2 169 2 168 2 167 2 166 2 165 2 164 2 163 2 162 2 161 2 160 2 159 2 158 2 157 2 156 2 155 2 154 2 153 2 15...
result:
ok good solution!
Test #54:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
299 BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
148 1 2 1 2 1 2 194 2 194 3 193 2 192 2 191 2 190 2 189 2 188 2 187 2 186 2 185 2 184 2 183 2 182 2 181 2 180 2 179 2 178 2 177 2 176 2 175 2 174 2 173 2 172 2 171 2 170 2 169 2 168 2 167 2 166 2 165 2 164 2 163 2 162 2 161 2 160 2 159 2 158 2 157 2 156 2 155 2 154 2 153 2 152 2 151 2 150 2 149 2 14...
result:
ok good solution!
Test #55:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
297 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA
output:
148 74 2 73 2 73 2 72 2 71 2 70 2 69 2 68 2 67 2 66 2 65 2 64 2 63 2 62 2 61 2 60 2 59 2 58 2 57 2 56 2 55 2 54 2 53 2 52 2 51 2 50 2 49 2 48 2 47 2 46 2 45 2 44 2 43 2 42 2 41 2 40 2 39 2 38 2 37 2 36 2 35 2 34 2 33 2 32 2 31 2 30 2 29 2 28 2 27 2 26 2 25 2 24 2 23 2 22 2 21 2 20 2 19 2 18 2 17 2 1...
result:
ok good solution!
Test #56:
score: -6
Runtime Error
input:
300 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
result:
Subtask #3:
score: 0
Wrong Answer
Test #102:
score: 7
Accepted
time: 33ms
memory: 3832kb
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 3995 2 3995 2 3995 2 3995 3 3994 2 3993 2 3992 2 3991 2 3990 2 3989 2 3988 2 3987 2 3986 2 3985 2 3984 2 3983 2 3982 2 3981 2 3980 2 3979 2 3978 2 3977 2 3976 2 3975 2 3974 2 3973 2 3972 2 3971 2 3970 2 3969 2 3968 2 3967 2 3966 2 3965 2 3964 2 3963 2 3962 2 3961 2 3960 2 3959 2 3958 2 3957 2 3...
result:
ok good solution!
Test #103:
score: 0
Accepted
time: 19ms
memory: 3956kb
input:
5999 BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 1 2 1 3 3995 2 3995 3 3994 2 3993 2 3992 2 3991 2 3990 2 3989 2 3988 2 3987 2 3986 2 3985 2 3984 2 3983 2 3982 2 3981 2 3980 2 3979 2 3978 2 3977 2 3976 2 3975 2 3974 2 3973 2 3972 2 3971 2 3970 2 3969 2 3968 2 3967 2 3966 2 3965 2 3964 2 3963 2 3962 2 3961 2 3960 2 3959 2 3958 2 3957 2 3956 2 ...
result:
ok good solution!
Test #104:
score: 0
Accepted
time: 28ms
memory: 3712kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2998 1499 3 1498 3 1497 2 1496 2 1495 2 1494 2 1493 2 1492 2 1491 2 1490 2 1489 2 1488 2 1487 2 1486 2 1485 2 1484 2 1483 2 1482 2 1481 2 1480 2 1479 2 1478 2 1477 2 1476 2 1475 2 1474 2 1473 2 1472 2 1471 2 1470 2 1469 2 1468 2 1467 2 1466 2 1465 2 1464 2 1463 2 1462 2 1461 2 1460 2 1459 2 1458 2 1...
result:
ok good solution!
Test #105:
score: -7
Wrong Answer
time: 1ms
memory: 3640kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
-1
result:
wrong answer you didn't find a solution but jury did
Subtask #4:
score: 0
Time Limit Exceeded
Test #153:
score: 0
Time Limit Exceeded
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...