結果

問題 No.1020 Reverse
ユーザー chocoruskchocorusk
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_popcount
using 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0