結果
問題 | No.1020 Reverse |
ユーザー |
![]() |
提出日時 | 2020-04-01 12:50:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,971 bytes |
コンパイル時間 | 1,503 ms |
コンパイル使用メモリ | 122,512 KB |
実行使用メモリ | 20,992 KB |
最終ジャッジ日時 | 2024-06-26 09:04:59 |
合計ジャッジ時間 | 2,839 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 WA * 14 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;struct SplayNode{SplayNode *l, *r, *p;int sz; char val;bool rev;SplayNode(char val):val(val), sz(1), rev(false), l(nullptr), r(nullptr){}void toggle(){this->rev^=true;swap(this->l, this->r);}void push(){if(this->rev){if(this->l) this->l->toggle();if(this->r) this->r->toggle();this->rev=false;}}void update(){this->sz=1;if(this->l) this->sz+=this->l->sz;if(this->r) this->sz+=this->r->sz;}void rotate(){SplayNode *p=this->p, *pp=p->p, *ch;if(p->l==this) ch=this->r;else ch=this->l;if(pp){if(pp->l==p) pp->l=this;else pp->r=this;}this->p=pp;if(p->l==this) this->r=p;else this->l=p;p->p=this;if(p->l==this) p->l=ch;else p->r=ch;if(ch) ch->p=p;p->update();update();}int state(){if(!this->p) return 0;else if(this->p->l==this) return 1;else return -1;}void splay(){push();while(this->p){if(!this->p->p){this->p->push(); push();rotate();}else{this->p->p->push(); this->p->push(); push();if(this->p->state()==state()){this->p->rotate();rotate();}else{rotate();rotate();}}}}};using node=SplayNode;node *get(node *root, int idx){node *now=root;while(1){now->push();int lsize=(now->l?now->l->sz:0);if(idx<lsize) now=now->l;else if(idx==lsize){now->splay();return now;}else{idx-=lsize+1;now=now->r;}}}node *merge(node *l, node *r){if(!l) return r;if(!r) return l;l=get(l, l->sz-1);l->r=r;r->p=l;l->update();return l;}pair<node*, node*> split(node *t, int k){//[0, k), [k, n)if(!t) return make_pair(nullptr, nullptr);if(k==0) return make_pair(nullptr, t);else if(k==t->sz) return make_pair(t, nullptr);t=get(t, k);node *s=t->l;if(s) s->p=nullptr;t->l=nullptr;t->update();return make_pair(s, t);}int main(){int n, k;cin>>n>>k;string s;cin>>s;vector<node*> v(n);for(int i=0; i<n; i++){v[i]=new node(s[i]);if(i) v[i]->l=v[i-1], v[i-1]->p=v[i], v[i]->update();}node *root=v[n-1];for(int i=0; i<n-k+1; i++){auto p=split(root, i);auto q=split(p.second, k);if(q.first) q.first->toggle(), q.first->push();root=merge(p.first, merge(q.first, q.second));}string ans;auto dfs=[&](auto dfs, node *now){if(!now) return;dfs(dfs, now->l);ans+=now->val;dfs(dfs, now->r);};dfs(dfs, root);cout<<ans<<endl;return 0;}