結果
| 問題 | No.1405 ジグザグロボット |
| ユーザー |
 register
|
| 提出日時 | 2024-06-07 23:41:35 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 7 ms / 3,153 ms |
| コード長 | 9,777 bytes |
| コンパイル時間 | 2,646 ms |
| コンパイル使用メモリ | 203,292 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-26 10:57:17 |
| 合計ジャッジ時間 | 7,599 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
コンパイルメッセージ
main.cpp:119:49: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
119 | void upd(int l,int r,int pos,int x,sb v,auto f){
| ^~~~
main.cpp:126:50: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
126 | void add(int l,int r,int pos,int x,int v,auto f){
| ^~~~
ソースコード
#include<bits/stdc++.h>using namespace std;struct __INIT__{__INIT__(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}}__INIT__;typedef long long lint;#define INF (1LL<<60)#define IINF (1<<30)#define endl ('\n')typedef vector<lint> vec;#define _overload4(_1,_2,_3,_4,name,...) name#define __rep(i,a) repi(i,0,a,1)#define _rep(i,a,b) repi(i,a,b,1)#define repi(i,a,b,c) for(long long i=(long long)(a);i<(long long)(b);i+=c)#define rep(...) _overload4(__VA_ARGS__,repi,_rep,__rep)(__VA_ARGS__)#define all(n) begin(n),end(n)template<typename T,typename E>bool chmin(T& s,const E& t){bool res=s>t;s=min<T>(s,t);return res;}template<typename T,typename E>bool chmax(T& s,const E& t){bool res=s<t;s=max<T>(s,t);return res;}template<typename T>struct maybe{bool _is_none;T val;maybe():_is_none(true){}maybe(T val):_is_none(false),val(val){}T unwrap()const{assert(!_is_none);return val;}T unwrap_or(T e)const{return _is_none?e:val;}bool is_none()const{return _is_none;}bool is_some()const{return !_is_none;}};template<typename T,typename F>auto expand(F op){return [&op](const maybe<T>& s,const maybe<T>& t){if(s.is_none())return t;if(t.is_none())return s;return maybe<T>(op(s.unwrap(),t.unwrap()));};}template<typename T,typename F>class segment_tree{maybe<T>* node;F op;int n=1;public:segment_tree(){}segment_tree(int sz,F op=F()):op(op){while(n<=sz)n<<=1;node=new maybe<T>[n*2];for(int i=0;i<n*2;i++)node[i]=maybe<T>();}segment_tree(const std::vector<T>&v,F op=F()):op(op){auto f=expand<T,F>(op);const int sz=v.size();while(n<=sz)n<<=1;node=new maybe<T>[n*2]();for(int i=0;i<sz;i++)node[i+n]=maybe<T>(v[i]);for(int i=n-1;i>=1;i--)node[i]=f(node[i*2],node[i*2+1]);}maybe<T> get(int l,int r){auto f=expand<T,F>(op);l+=n;r+=n;maybe<T> s,t;while(l<r){if(l&1)s=f(s,node[l++]);if(r&1)t=f(node[--r],t);l>>=1;r>>=1;}return f(s,t);}void apply(int t,T _val){auto f=expand<T,F>(op);t+=n;maybe<T> val=maybe<T>(_val);while(t){node[t]=f(node[t],val);t=t>>1;}}void apply_left(int t,T _val){auto f=expand<T,F>(op);t+=n;maybe<T> val=maybe<T>(_val);while(t){node[t]=f(val,node[t]);t=t>>1;}}void change(int t,T val){auto f=expand<T,F>(op);t+=n;node[t]=maybe<T>(val);while(t>1){t=t>>1;node[t]=f(node[t*2],node[t*2+1]);}}};using sb=array<lint,2>;#define lc pos<<1#define rc pos<<1|1#define mid ((l+r)>>1)class weishashi4logde{vector<sb> tr;vector<int> tg;public:weishashi4logde(int sz){int n=sz+1;tr.resize(n*4+1,{-INF,0});tg.resize(n*4+1);}void cov(int x,int v) {tr[x][0]+=v;tg[x]+=v;}void pushdown(int pos){int&t=tg[pos];if(t) cov(lc,t),cov(rc,t),t=0;}void upd(int l,int r,int pos,int x,sb v,auto f){if(l==r) {tr[pos]=v;return;}pushdown(pos);if(x<=mid) upd(l,mid,lc,x,v,f);else upd(mid+1,r,rc,x,v,f);tr[pos]=f(tr[lc],tr[rc]);}void add(int l,int r,int pos,int x,int v,auto f){if(r<=x) return cov(pos,v);pushdown(pos);add(l,mid,lc,x,v,f);if(x>mid) add(mid+1,r,rc,x,v,f);tr[pos]=f(tr[lc],tr[rc]);}sb ask() {return tr[1];}};template<typename F,typename T=long long>T bs(T mn,T mx,F func){mn--;mx++;while(mx-mn>1){T md=(mn+mx)/2;if(!func(md))mx=md;else mn=md;}return mn;}int main(){lint n,x,y;cin>>n>>x>>y;string s;cin>>s;vector<tuple<lint,lint,lint,lint,lint>>v;lint p=0,q=0,cnt=0,cnt_mx=0;vec edge;vector<lint>spos;vector<pair<lint,lint>> vv;if(count(all(s),'S')<y){cout<<-1<<endl;return 0;}rep(i,n){if(s[i]=='S'){spos.push_back(i);edge.push_back(cnt);vv.push_back(make_pair(p,q));cnt++;cnt_mx++;p=q=0;}if(s[i]=='R'){q++;chmin(p,q);}if(s[i]=='L'){q--;chmin(p,q);}}edge.push_back(cnt);vv.push_back(make_pair(p,q));cnt++;cnt_mx++;auto get=[&](pair<lint,lint>x){return x.second-x.first;};auto merge=[&](pair<lint,lint>s,pair<lint,lint>t){return make_pair(min(s.first,s.second+t.first),s.second+t.second);};segment_tree<pair<lint,lint>,decltype(merge)>seg(vv,merge);lint pena=bs(-n,n,[&](lint x){vector<lint>dp(cnt+1,-INF);vector<lint>d(cnt+1,-INF);dp[0]=d[0]=0;int now=0;auto mer=[&](sb s,sb t){auto _s=s,_t=t;_s[1]=-d[s[1]];_t[1]=-d[t[1]];return _s>_t?s:t;};weishashi4logde shabi(cnt);shabi.upd(0,cnt,1,0,sb{0,0},mer);stack<int> stk;rep(i,n){if(s[i]=='S'){now++;auto t=shabi.ask();dp[now]=t[0]-x;d[now]=d[t[1]]+1;shabi.upd(0,cnt,1,now,sb{dp[now],now},mer);}if(s[i]=='L'&&stk.size()){int tp=stk.top();stk.pop();shabi.add(0,cnt,1,tp,-1,mer);}if(s[i]=='R') shabi.add(0,cnt,1,now,1,mer),stk.push(now);}auto t=shabi.ask();dp[cnt]=t[0]-x;d[cnt]=d[t[1]]+1;return d[cnt]>y+1;})+1;vector<lint>a,b;{vector<lint>dp(cnt+1,-INF);vector<lint>d(cnt+1,-INF);vector<lint>from(cnt+1,-1);dp[0]=d[0]=0;int now=0;auto mer=[&](sb s,sb t){auto _s=s,_t=t;_s[1]=-d[s[1]];_t[1]=-d[t[1]];return _s>_t?s:t;};weishashi4logde shabi(cnt);shabi.upd(0,cnt,1,0,sb{0,0},mer);stack<int> stk;rep(i,n){if(s[i]=='S'){now++;auto t=shabi.ask();dp[now]=t[0]-pena;d[now]=d[t[1]]+1;from[now]=t[1];shabi.upd(0,cnt,1,now,sb{dp[now],now},mer);}if(s[i]=='L'&&stk.size()){int tp=stk.top();stk.pop();shabi.add(0,cnt,1,tp,-1,mer);}if(s[i]=='R') shabi.add(0,cnt,1,now,1,mer),stk.push(now);}auto t=shabi.ask();dp[cnt]=t[0]-pena;d[cnt]=d[t[1]]+1;from[cnt]=t[1];now=cnt;while(now!=-1){a.push_back(now);now=from[now];}reverse(all(a));}{vector<lint>dp(cnt+1,-INF);vector<lint>d(cnt+1,-INF);vector<lint>from(cnt+1,-1);dp[0]=d[0]=0;int now=0;auto mer=[&](sb s,sb t){auto _s=s,_t=t;_s[1]=d[s[1]];_t[1]=d[t[1]];return _s>_t?s:t;};weishashi4logde shabi(cnt);shabi.upd(0,cnt,1,0,sb{0,0},mer);stack<int> stk;rep(i,n){if(s[i]=='S'){now++;auto t=shabi.ask();dp[now]=t[0]-pena;d[now]=d[t[1]]+1;from[now]=t[1];shabi.upd(0,cnt,1,now,sb{dp[now],now},mer);}if(s[i]=='L'&&stk.size()){int tp=stk.top();stk.pop();shabi.add(0,cnt,1,tp,-1,mer);}if(s[i]=='R') shabi.add(0,cnt,1,now,1,mer),stk.push(now);}auto t=shabi.ask();dp[cnt]=t[0]-pena;d[cnt]=d[t[1]]+1;from[cnt]=t[1];now=cnt;while(now!=-1){b.push_back(now);now=from[now];}reverse(all(b));}vec c,d;lint ai=0,bi=0;while(ai<(int)a.size()||bi<(int)b.size()){if((int)a.size()-ai+(int)c.size()==y+2||(int)b.size()-bi+(int)d.size()==y+2){if(ai<(int)a.size())c.push_back(a[ai++]);if(bi<(int)b.size())d.push_back(b[bi++]);}else if(ai<(int)a.size()&&bi+1<(int)b.size()&&a[ai]==b[bi+1]){c.push_back(a[ai++]);d.push_back(b[bi++]);d.push_back(b[bi++]);c.swap(d);}else if(ai<(int)a.size()&&bi+1<(int)b.size()&&a[ai]>b[bi+1]){d.push_back(b[bi++]);c.swap(d);}else{if(ai<(int)a.size())c.push_back(a[ai++]);if(bi<(int)b.size())d.push_back(b[bi++]);}}vec vvv(y+1),ll(y+1),rr(y+1);{if((int)c.size()!=y+2){c.swap(d);}rep(i,c.size()-1){vvv[i]=get(seg.get(c[i],c[i+1]).unwrap());ll[i]=c[i];rr[i]=c[i+1];}}vector<pair<lint,lint>> ans;ans.emplace_back(-1,0);lint nx=0;for(int ny=0;ny<=y;++ny){lint px=nx;if(nx==x){ans.emplace_back(x-1,ny);ans.emplace_back(x+1,ny);}else if(nx+vvv[ny]>x){lint p=0,q=0,r=0;rep(i,ll[ny],rr[ny]){if(s[i]=='R'){q++;chmax(r,q);if(chmin(p,q)){r=0;}}if(s[i]=='L'){q--;chmax(r,q);if(chmin(p,q)){r=0;}}}nx=x;rep(i,px-1,nx){ans.emplace_back(i,ny+1);}rep(i,0,ny+1)ans.emplace_back(x+r-q+1,i);rep(i,x+1,x+r-q+1)ans.emplace_back(i,ny+1);}else{nx+=vvv[ny];rep(i,px-1,nx){ans.emplace_back(i,ny+1);}}}rep(i,n)ans.emplace_back(i,y+1);if(x!=nx){cout<<-1<<endl;return 0;}cout<<ans.size()<<endl;for(auto&o:ans){lint s,t;tie(s,t)=o;cout<<s<<" "<<t<<endl;}}