結果

問題 No.1020 Reverse
ユーザー chocoruskchocorusk
提出日時 2020-04-01 12:50:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 2,986 bytes
コンパイル時間 1,174 ms
コンパイル使用メモリ 121,488 KB
実行使用メモリ 20,992 KB
最終ジャッジ日時 2024-06-26 09:06:00
合計ジャッジ時間 2,296 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 27 ms
13,184 KB
testcase_08 AC 29 ms
14,720 KB
testcase_09 AC 20 ms
13,312 KB
testcase_10 AC 47 ms
19,328 KB
testcase_11 AC 40 ms
18,304 KB
testcase_12 AC 39 ms
17,920 KB
testcase_13 AC 44 ms
19,072 KB
testcase_14 AC 38 ms
18,048 KB
testcase_15 AC 20 ms
13,824 KB
testcase_16 AC 21 ms
14,080 KB
testcase_17 AC 49 ms
20,992 KB
権限があれば一括ダウンロードができます

ソースコード

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;
		now->push();
		dfs(dfs, now->l);
		ans+=now->val;
		dfs(dfs, now->r);
	};
	dfs(dfs, root);
	cout<<ans<<endl;
	return 0;
}
0