QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#134199#4273. Good Gameblackyuki0 33ms3956kbC++144.7kb2023-08-03 13:11:462023-08-03 13:12:16

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 13:12:16]
  • 评测
  • 测评结果:0
  • 用时:33ms
  • 内存:3956kb
  • [2023-08-03 13:11:46]
  • 提交

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;
}

詳細信息

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...

output:


result: