Submission #92506


Source Code Expand

Copy
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

#define REP(i,x) for(int i=0 ; i<(int)(x) ; i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

struct Node{
	string s;// if this node is leaf, s is not empty string. 
	LL repeat;
	vector<Node> children;
	LL size;
	Node():s(""),size(-1),repeat(1){}
	LL getSize(){
		if(size!=-1)return size;
		size = 0;
		REP(i,children.size()){
			size += children[i].getSize();
		}
		size *= repeat;
		return size;
	}
};

bool parseString(const string& s,int& idx,Node &next);

void parseInput(const string& s,int& idx,vector<Node> &strings){
	while(idx<(int)s.size()){
		Node next;
		if(!parseString(s,idx,next))return;
		strings.push_back(next);
	}
}

bool parseString(const string& s,int& idx,Node &next){
	if(isalpha(s[idx])){
		while(idx<(int)s.size() && isalpha(s[idx])){
			next.s.push_back(s[idx]);
			idx++;
		}
		next.size = next.s.size();
	}else if(s[idx]=='('){
		idx++;
		parseInput(s,idx,next.children);
		idx++;
		next.repeat = 0;
		while(idx<(int)s.size() && isdigit(s[idx])){
			next.repeat = 10LL*next.repeat+s[idx]-'0';
			idx++;
		}
	}else return false;
	return true;
}

void trav(Node &node,LL start,LL end,string &res){
	//cout << start << " " << end << endl;
	if(!node.s.empty()){
		for(LL i = start ; i<end ; i++)res += node.s[i];
	}else{
		LL sum = 0;
		LL c = node.getSize()/node.repeat;
		LL rs = start/c;
		for(int r = max(0,(int)rs-1) ; r<(int)node.repeat ; r++){
			REP(i,node.children.size()){
				LL prev = sum;
				sum += node.children[i].getSize();
				if(start<sum && prev<end){
					trav(node.children[i],max(prev,start)-prev,min(sum,end)-prev,res);
				}
			}
			if(sum>end)break;
		}
	}
}

int main(){
	for(LL B,L,N ; cin>>B>>L>>N ; ){
		string s;
		cin >> s;
		int idx = 0;
		Node tree;
		parseInput(s,idx,tree.children);
		B = (B+tree.getSize())%tree.getSize();
		//cout << B << endl;
		string res = "";
		trav(tree,B,B+L,res);
		cout << res << endl;
	}
}

Submission Info

Submission Time
Task D - 天下一展開
User nel215
Language C++ (G++ 4.6.4)
Score 0
Code Size 2304 Byte
Status WA
Exec Time 2039 ms
Memory 2740 KB

Judge Result

Set Name small medium large
Score / Max Score 0 / 50 0 / 50 0 / 30
Status
AC × 29
WA × 5
AC × 42
WA × 20
TLE × 4
AC × 45
WA × 34
TLE × 10
Set Name Test Cases
small small, small/01_manual1, small/01_manual2, small/01_sample2, small/10_manual3, small/11_small00, small/11_small01, small/11_small02, small/11_small03, small/11_small04, small/11_small05, small/11_small06, small/11_small07, small/11_small08, small/11_small09, small/11_small10, small/11_small11, small/11_small12, small/11_small13, small/11_small14, small/11_small15, small/11_small16, small/11_small17, small/11_small18, small/11_small19, small/11_small20, small/11_small21, small/11_small22, small/11_small23, small/11_small24, small/11_small25, small/11_small26, small/11_small27, small/11_small28, small/11_small29
medium small, small/01_manual1, small/01_manual2, small/01_sample2, small/10_manual3, small/11_small00, small/11_small01, small/11_small02, small/11_small03, small/11_small04, small/11_small05, small/11_small06, small/11_small07, small/11_small08, small/11_small09, small/11_small10, small/11_small11, small/11_small12, small/11_small13, small/11_small14, small/11_small15, small/11_small16, small/11_small17, small/11_small18, small/11_small19, small/11_small20, small/11_small21, small/11_small22, small/11_small23, small/11_small24, small/11_small25, small/11_small26, small/11_small27, small/11_small28, small/11_small29, medium, medium/20_manual5, medium/20_manual6, medium/21_medium30, medium/21_medium31, medium/21_medium32, medium/21_medium33, medium/21_medium34, medium/21_medium35, medium/21_medium36, medium/21_medium37, medium/21_medium38, medium/21_medium39, medium/21_medium40, medium/21_medium41, medium/21_medium42, medium/21_medium43, medium/21_medium44, medium/21_medium45, medium/21_medium46, medium/21_medium47, medium/21_medium48, medium/21_medium49, medium/21_medium50, medium/21_medium51, medium/21_medium52, medium/21_medium53, medium/21_medium54, medium/21_medium55, medium/21_medium56, medium/21_medium57, medium/21_medium58, medium/21_medium59
large large, medium, small, large/30_manual4, large/30_manual7, large/31_large60, large/31_large61, large/31_large62, large/31_large63, large/31_large64, large/31_large65, large/31_large66, large/31_large67, large/31_large68, large/31_large69, large/32_large70, large/32_large71, large/32_large72, large/32_large73, large/32_large74, large/32_large75, large/32_large76, large/32_large77, large/32_large78, large/32_large79, large/33_large80, medium/20_manual5, medium/20_manual6, medium/21_medium30, medium/21_medium31, medium/21_medium32, medium/21_medium33, medium/21_medium34, medium/21_medium35, medium/21_medium36, medium/21_medium37, medium/21_medium38, medium/21_medium39, medium/21_medium40, medium/21_medium41, medium/21_medium42, medium/21_medium43, medium/21_medium44, medium/21_medium45, medium/21_medium46, medium/21_medium47, medium/21_medium48, medium/21_medium49, medium/21_medium50, medium/21_medium51, medium/21_medium52, medium/21_medium53, medium/21_medium54, medium/21_medium55, medium/21_medium56, medium/21_medium57, medium/21_medium58, medium/21_medium59, small/01_manual1, small/01_manual2, small/01_sample2, small/10_manual3, small/11_small00, small/11_small01, small/11_small02, small/11_small03, small/11_small04, small/11_small05, small/11_small06, small/11_small07, small/11_small08, small/11_small09, small/11_small10, small/11_small11, small/11_small12, small/11_small13, small/11_small14, small/11_small15, small/11_small16, small/11_small17, small/11_small18, small/11_small19, small/11_small20, small/11_small21, small/11_small22, small/11_small23, small/11_small24, small/11_small25, small/11_small26, small/11_small27, small/11_small28, small/11_small29
Case Name Status Exec Time Memory
large/30_manual4 WA 20 ms 788 KB
large/30_manual7 WA 139 ms 1592 KB
large/31_large60 TLE 2028 ms 940 KB
large/31_large61 TLE 2028 ms 956 KB
large/31_large62 TLE 2029 ms 924 KB
large/31_large63 TLE 2028 ms 884 KB
large/31_large64 WA 35 ms 788 KB
large/31_large65 TLE 2028 ms 824 KB
large/31_large66 WA 1021 ms 656 KB
large/31_large67 TLE 2028 ms 960 KB
large/31_large68 AC 1766 ms 820 KB
large/31_large69 WA 1030 ms 796 KB
large/32_large70 WA 279 ms 1720 KB
large/32_large71 WA 267 ms 1724 KB
large/32_large72 WA 269 ms 1732 KB
large/32_large73 WA 276 ms 1724 KB
large/32_large74 AC 1067 ms 2740 KB
large/32_large75 WA 541 ms 2492 KB
large/32_large76 WA 533 ms 2496 KB
large/32_large77 WA 540 ms 2492 KB
large/32_large78 WA 547 ms 2480 KB
large/32_large79 WA 550 ms 2468 KB
large/33_large80 AC 32 ms 1468 KB
medium/20_manual5 WA 20 ms 780 KB
medium/20_manual6 WA 19 ms 660 KB
medium/21_medium30 AC 18 ms 784 KB
medium/21_medium31 AC 1178 ms 788 KB
medium/21_medium32 AC 19 ms 772 KB
medium/21_medium33 WA 393 ms 784 KB
medium/21_medium34 AC 19 ms 812 KB
medium/21_medium35 AC 19 ms 792 KB
medium/21_medium36 AC 706 ms 788 KB
medium/21_medium37 AC 731 ms 820 KB
medium/21_medium38 AC 20 ms 688 KB
medium/21_medium39 WA 21 ms 792 KB
medium/21_medium40 TLE 2035 ms 812 KB
medium/21_medium41 WA 111 ms 788 KB
medium/21_medium42 AC 114 ms 792 KB
medium/21_medium43 AC 29 ms 788 KB
medium/21_medium44 WA 179 ms 684 KB
medium/21_medium45 TLE 2039 ms 820 KB
medium/21_medium46 WA 673 ms 784 KB
medium/21_medium47 AC 363 ms 788 KB
medium/21_medium48 AC 1290 ms 788 KB
medium/21_medium49 WA 22 ms 764 KB
medium/21_medium50 WA 53 ms 792 KB
medium/21_medium51 WA 20 ms 788 KB
medium/21_medium52 AC 1535 ms 784 KB
medium/21_medium53 TLE 2028 ms 824 KB
medium/21_medium54 TLE 2029 ms 824 KB
medium/21_medium55 WA 387 ms 792 KB
medium/21_medium56 WA 1102 ms 784 KB
medium/21_medium57 WA 309 ms 784 KB
medium/21_medium58 WA 604 ms 788 KB
medium/21_medium59 WA 20 ms 692 KB
small/01_manual1 AC 19 ms 788 KB
small/01_manual2 WA 20 ms 692 KB
small/01_sample2 AC 18 ms 796 KB
small/10_manual3 AC 20 ms 788 KB
small/11_small00 AC 20 ms 792 KB
small/11_small01 AC 20 ms 788 KB
small/11_small02 WA 21 ms 696 KB
small/11_small03 AC 20 ms 788 KB
small/11_small04 AC 19 ms 784 KB
small/11_small05 AC 20 ms 792 KB
small/11_small06 WA 19 ms 788 KB
small/11_small07 AC 20 ms 788 KB
small/11_small08 AC 20 ms 696 KB
small/11_small09 AC 19 ms 808 KB
small/11_small10 AC 19 ms 784 KB
small/11_small11 AC 20 ms 784 KB
small/11_small12 AC 20 ms 784 KB
small/11_small13 AC 19 ms 788 KB
small/11_small14 WA 20 ms 788 KB
small/11_small15 AC 20 ms 788 KB
small/11_small16 AC 20 ms 784 KB
small/11_small17 AC 19 ms 668 KB
small/11_small18 AC 19 ms 772 KB
small/11_small19 AC 20 ms 700 KB
small/11_small20 AC 20 ms 784 KB
small/11_small21 WA 21 ms 792 KB
small/11_small22 AC 20 ms 792 KB
small/11_small23 AC 19 ms 704 KB
small/11_small24 AC 19 ms 788 KB
small/11_small25 AC 20 ms 800 KB
small/11_small26 AC 20 ms 800 KB
small/11_small27 AC 20 ms 660 KB
small/11_small28 AC 20 ms 660 KB
small/11_small29 AC 20 ms 792 KB