結果
| 問題 | No.1405 ジグザグロボット |
| ユーザー |
 register
|
| 提出日時 | 2024-06-08 00:08:14 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 8 ms / 3,153 ms |
| コード長 | 7,269 bytes |
| コンパイル時間 | 4,451 ms |
| コンパイル使用メモリ | 199,032 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-26 11:42:48 |
| 合計ジャッジ時間 | 10,719 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
コンパイルメッセージ
main.cpp:35:49: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
35 | void upd(int l,int r,int pos,int x,sb v,auto f){
| ^~~~
main.cpp:42:50: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
42 | 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;}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(){//freopen("robot.in","r",stdin);//freopen("robot.out","w",stdout);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;vec edge;vector<lint>spos;vector<pair<lint,lint>> vv;if((cnt=count(all(s),'S'))<y){cout<<-1<<endl;return 0;}cnt++;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);}int p=0;rep(i,c.size()-1){int v=0;for(int t=c[i+1]-c[i];p<n&&t;p++)if(s[p]=='S') t--;else if(s[p]=='L') v=max(v-1,0);else v++;vvv[i]=v;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;}}