QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#134127 | #4273. Good Game | blackyuki | 0 | 19ms | 40652kb | C++14 | 3.7kb | 2023-08-03 07:50:42 | 2023-08-03 07:50:45 |
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);}
void sol(ll n,string s){
vp v;
rep(i,n){
if(i==0||s[i]!=s[i-1])v.pb(i,i);
else v.back().se++;
}
vp waiting,ans;
auto del=[&](ll a,ll b){
while(a<=b){
ll d=2;
if(b-a==2)d=3;
ans.pb(a+1,d);
b-=d;
}
};
while(v.size()){
while(v.size()&&(waiting.size()==0||(v.back().fi==v.back().se)==(waiting.back().fi==waiting.back().se))){
waiting.pb(v.back());
v.pop_back();
}
if(v.size()==0)break;
if(waiting.back().fi==waiting.back().se){
del(v.back().fi,v.back().se);
v.pop_back();
if(v.size()){
v.back().se+=waiting.back().se-waiting.back().fi+1;
waiting.pop_back();
}
}
else{
del(v.back().se+1,v.back().se+1+waiting.back().se-waiting.back().fi);
waiting.pop_back();
if(waiting.size()){
v.back().se+=waiting.back().se-waiting.back().fi+1;
waiting.pop_back();
}
}
}
while(v.size()){
if(v.back().fi==v.back().se){
out(-1);return;
}
del(v.back().fi,v.back().se);
v.pop_back();
}
while(waiting.size()){
if(waiting.back().fi==waiting.back().se){
out(-1);return;
}
del(0,waiting.back().se-waiting.back().fi);
waiting.pop_back();
}
out(ans.size());
for(auto x:ans)cout<<x.fi<<' '<<x.se<<endl;
}
int main(){
ll n;cin>>n;
string s;cin>>s;
sol(n,s);
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 1ms
memory: 3504kb
input:
9 ABAABBBAA
output:
4 3 2 2 2 2 2 1 3
result:
ok good solution!
Test #2:
score: -3
Wrong Answer
time: 1ms
memory: 3444kb
input:
13 ABABBABABBABA
output:
-1
result:
wrong answer you didn't find a solution but jury did
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 6
Accepted
time: 1ms
memory: 3440kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
-1
result:
ok no solution
Test #52:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
300 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...
output:
-1
result:
ok no solution
Test #53:
score: -6
Wrong Answer
time: 1ms
memory: 3460kb
input:
299 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
-1
result:
wrong answer you didn't find a solution but jury did
Subtask #3:
score: 0
Wrong Answer
Test #102:
score: 0
Wrong Answer
time: 1ms
memory: 3580kb
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
-1
result:
wrong answer you didn't find a solution but jury did
Subtask #4:
score: 0
Wrong Answer
Test #153:
score: 0
Wrong Answer
time: 19ms
memory: 40652kb
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
-1
result:
wrong answer you didn't find a solution but jury did