Submission #93107


Source Code Expand

Copy
#include <iostream>
#include <cassert>
#include <string>
#include <cctype>
#include <map>
using namespace std;

typedef long long ll;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

map<size_t, ll> length;
map<size_t, size_t> next_cur;

ll size(const string &str, size_t &cur);

ll Number(const string &str, size_t &cur){
  ll res = 0;
  while(cur < str.size() && isdigit(str[cur])){
    res = res * 10 + str[cur++] - '0';
  }
  return res;
}

string String(const string &str, size_t &cur){
  ll l = cur;
  assert(isalpha(str[cur]));
  while(cur < str.size() && isalpha(str[cur])) cur++;
  return string(str.begin() + l, str.begin() + cur);
}

ll size_str(const string &str, size_t &cur){
  if(str[cur] == '('){
    ll len = size(str, ++cur);
    assert(str[cur++] == ')');
    return len * Number(str, cur);
  }else{
    return String(str, cur).size();
  }
}

ll size(const string &str, size_t &cur){
  size_t pos = cur;
  if(length.find(pos) != length.end()){
    cur = next_cur[pos];
    return length[pos];
  }
  
  ll s = size_str(str, cur);
  while(cur < str.size() && str[cur] != ')'){
    s += size_str(str, cur);
  }

  next_cur[pos] = cur;
  return length[pos] = s;
}

ll size(const string &str){
  size_t cur = 0;
  return size(str, cur);
}

string expr(const string &str, size_t &cur, ll s, ll e);

string exp_str(const string &str, size_t &cur, ll s, ll e){
  assert(e - s <= 100000);
  if(s >= e) return string("");
  
  if(str[cur] == '('){
    string ans(e - s, ' ');
    string ret;
    string full;
    
    size_t tot = 0;
    
    size_t old_cur = ++cur;
    ll len = size(str, cur);
    assert(str[cur++] == ')');
    ll tot_len = len * Number(str, cur);
    ll start = s / len * len;

    while(start < e && start < tot_len){
      size_t tmp_cur = old_cur;
      ll tmp_s = max(0LL, s - start);
      ll tmp_e = min(max(0LL, e - start), len);
      
      if(tmp_e - tmp_s == len){
	if(full == ""){
	  full = ret = expr(str, tmp_cur, tmp_s, tmp_e);
	}else{
	  ret = full;
	}
      }else{
	ret = expr(str, tmp_cur, tmp_s, tmp_e);
      }
      REP(i, ret.size()) ans[tot + i] = ret[i];
      tot += ret.size();
      start += len;
    }
    assert(ans.size() == tot);
    return ans;
  }else{
    string t = String(str, cur);
    return string(t.begin() + s, t.begin() + e);
  }
};

string expr(const string &str, size_t &cur, ll s, ll e){
  if(s >= e) string("");;
  string ans(e - s, ' ');
  string ret;
  size_t tot = 0;
  size_t len_cur = cur;
  ll len = size_str(str, len_cur);
  
  if(s < min(len, e)){
    ret = exp_str(str, cur, s, min(len, e));
    REP(i, ret.size()) ans[i] = ret[i];
    tot += ret.size();
  }
  
  cur = len_cur;
  s = max(0LL, s - len);
  e = max(0LL, e - len);
  
  while(cur < str.size() && str[cur] != ')'){
    ll len = size_str(str, len_cur);
    if(s < min(len, e)){
      ret = exp_str(str, cur, s, min(len, e));
      REP(i, ret.size()) ans[tot + i] = ret[i];
      tot += ret.size();
    }
    cur = len_cur;
    s = max(0LL, s - len);
    e = max(0LL, e - len);
  }
  
  // cout << tot << " " << ans.size()
  //      << " " << s << " " << e << endl
  // cout << ans << endl;
  
  assert(tot == ans.size());
  return ans;
}
		
string solve(const string &str, ll s, ll e){
  size_t cur = 0;
  return expr(str, cur, s, e);
}


int main(){
  ll B, L, N;
  string S;
  cin >> B >> L >> N >> S;
  length[0] = size(S);
  if(B < 0) B = length[0] + B;
  cout << solve(S, B, B + L) << endl;
  return 0;
}

Submission Info

Submission Time
Task D - 天下一展開
User flowlight
Language C++ (G++ 4.6.4)
Score 0
Code Size 3620 Byte
Status WA
Exec Time 2054 ms
Memory 524944 KB

Judge Result

Set Name small medium large
Score / Max Score 0 / 50 0 / 50 0 / 30
Status
AC × 17
WA × 12
RE × 5
AC × 33
WA × 13
RE × 20
AC × 37
WA × 13
TLE × 4
MLE × 4
RE × 31
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 AC 22 ms 916 KB
large/30_manual7 RE 272 ms 1240 KB
large/31_large60 RE 258 ms 788 KB
large/31_large61 AC 42 ms 1500 KB
large/31_large62 RE 267 ms 1280 KB
large/31_large63 RE 261 ms 980 KB
large/31_large64 RE 255 ms 1044 KB
large/31_large65 RE 268 ms 1032 KB
large/31_large66 RE 251 ms 920 KB
large/31_large67 RE 261 ms 916 KB
large/31_large68 AC 24 ms 1048 KB
large/31_large69 RE 261 ms 1044 KB
large/32_large70 MLE 1084 ms 212796 KB
large/32_large71 MLE 1293 ms 258652 KB
large/32_large72 MLE 1170 ms 220104 KB
large/32_large73 MLE 950 ms 186684 KB
large/32_large74 TLE 2049 ms 468964 KB
large/32_large75 RE 267 ms 1880 KB
large/32_large76 TLE 2050 ms 480976 KB
large/32_large77 TLE 2022 ms 407988 KB
large/32_large78 TLE 2054 ms 524944 KB
large/32_large79 RE 279 ms 1976 KB
large/33_large80 AC 29 ms 1432 KB
medium/20_manual5 AC 35 ms 784 KB
medium/20_manual6 RE 243 ms 792 KB
medium/21_medium30 RE 260 ms 760 KB
medium/21_medium31 RE 259 ms 780 KB
medium/21_medium32 AC 22 ms 788 KB
medium/21_medium33 RE 253 ms 792 KB
medium/21_medium34 RE 256 ms 784 KB
medium/21_medium35 RE 250 ms 736 KB
medium/21_medium36 RE 253 ms 784 KB
medium/21_medium37 AC 21 ms 788 KB
medium/21_medium38 WA 23 ms 796 KB
medium/21_medium39 AC 23 ms 796 KB
medium/21_medium40 RE 257 ms 788 KB
medium/21_medium41 AC 22 ms 792 KB
medium/21_medium42 AC 20 ms 780 KB
medium/21_medium43 RE 259 ms 788 KB
medium/21_medium44 RE 263 ms 800 KB
medium/21_medium45 RE 252 ms 788 KB
medium/21_medium46 RE 250 ms 784 KB
medium/21_medium47 AC 26 ms 796 KB
medium/21_medium48 AC 52 ms 784 KB
medium/21_medium49 AC 23 ms 780 KB
medium/21_medium50 RE 264 ms 788 KB
medium/21_medium51 AC 22 ms 792 KB
medium/21_medium52 AC 21 ms 816 KB
medium/21_medium53 RE 256 ms 788 KB
medium/21_medium54 AC 23 ms 748 KB
medium/21_medium55 AC 24 ms 784 KB
medium/21_medium56 AC 21 ms 792 KB
medium/21_medium57 RE 251 ms 816 KB
medium/21_medium58 AC 22 ms 788 KB
medium/21_medium59 AC 22 ms 820 KB
small/01_manual1 AC 20 ms 784 KB
small/01_manual2 WA 22 ms 792 KB
small/01_sample2 RE 282 ms 824 KB
small/10_manual3 AC 37 ms 796 KB
small/11_small00 WA 23 ms 792 KB
small/11_small01 WA 41 ms 788 KB
small/11_small02 RE 271 ms 816 KB
small/11_small03 AC 23 ms 788 KB
small/11_small04 AC 22 ms 792 KB
small/11_small05 WA 22 ms 784 KB
small/11_small06 AC 22 ms 780 KB
small/11_small07 AC 22 ms 792 KB
small/11_small08 RE 265 ms 800 KB
small/11_small09 AC 22 ms 792 KB
small/11_small10 AC 27 ms 784 KB
small/11_small11 AC 25 ms 764 KB
small/11_small12 AC 21 ms 792 KB
small/11_small13 RE 263 ms 812 KB
small/11_small14 AC 23 ms 796 KB
small/11_small15 AC 26 ms 784 KB
small/11_small16 WA 33 ms 824 KB
small/11_small17 WA 32 ms 784 KB
small/11_small18 WA 28 ms 784 KB
small/11_small19 WA 28 ms 788 KB
small/11_small20 AC 25 ms 780 KB
small/11_small21 WA 25 ms 780 KB
small/11_small22 WA 25 ms 800 KB
small/11_small23 AC 36 ms 788 KB
small/11_small24 WA 22 ms 784 KB
small/11_small25 AC 85 ms 780 KB
small/11_small26 AC 22 ms 792 KB
small/11_small27 WA 83 ms 788 KB
small/11_small28 AC 23 ms 792 KB
small/11_small29 RE 297 ms 788 KB