Submission #92257


Source Code Expand

Copy
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cassert>
using namespace std;
typedef long long ll;

#define REP(i,n) for (ll i=0; i<(ll)(n); ++i)
#define FOR(i,k,n) for (ll i=(k); i<(ll)(n); ++i)
#define FOREQ(i,k,n) for (ll i=(k); i<=(ll)(n); ++i)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(v) (ll)((v).size())
#define MEMSET(v,h) memset((v),(h),sizeof(v))

struct Node {
  char t;
  ll len;
  ll loop;
  vector<Node*> ch;
  Node(){}

  void calc_len() {
    len = 0;
    FORIT(it, ch) len += (*it)->len;
    len *= loop;
  }
};

ll parse_digit();

string s;
ll ptr;
Node* parse() {
  if (ptr == SZ(s)) return NULL;

  Node* n = new Node();
  if (s[ptr]=='(') {
    ptr++;
    for (; s[ptr]!=')'; ) {
      n->ch.push_back(parse());
    }
    ptr++;
    ll loop = parse_digit();
    n->loop = loop;
    n->calc_len();
    n->t = 0;

    //cout<<"#"<<loop<<endl;
    return n;
  }

  n->t    = s[ptr];
  n->loop = 1;
  n->len  = 1;
  ptr++;
  return n;
}

ll parse_digit() {
  ll l = 0;
  assert(isdigit(s[ptr]));
  for (; ptr<SZ(s) && isdigit(s[ptr]); ) {
    l = l*10LL+(s[ptr]-'0');
    ptr++;
  }
  return l;
}

void get(Node* n, ll now, ll fr, ll to) {
  //cout<<"#"<<now<<" "<<n->len<<endl;
  if (now + n->len < fr || now >= to) return;

  if (n->len == 1 && fr <= now && now < to && n->t > 0) {
    putchar(n->t);
    return;
  }

  ll block = n->len/n->loop;
  ll lower = max(0LL,     (fr-now) / block);
  ll upper = min(n->loop, 1+(to-now) / block);
  /*
  ll
  lower = 0,
  upper = n->loop;
  */

  now += lower * block;
  FOR(iter, lower, upper) {
    FORIT(it, n->ch) {
      ll next = now + (*it)->len;

      get(*it, now, fr, to);

      now = next;
      //if (now > to) break;
    }
  }
}

char buf[10020];
int main() {
  ll B,L,N;
  while (cin >> B >> L >> N) {
    scanf(" %s", buf);
    s = "("+string(buf)+")1";

    ptr=0;
    Node* r = parse();

    //cout<<r->len<<endl;
    if (B < 0) B = r->len + B;

    //cout<<buf<<" "<<B<<" "<<L<<endl;
    get(r, 0, B, B+L);
    puts("");
  }
}

Submission Info

Submission Time
Task D - 天下一展開
User ir5
Language C++ (G++ 4.6.4)
Score 130
Code Size 2358 Byte
Status AC
Exec Time 585 ms
Memory 1412 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:113:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name small medium large
Score / Max Score 50 / 50 50 / 50 30 / 30
Status
AC × 34
AC × 66
AC × 89
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 21 ms 788 KB
large/30_manual7 AC 21 ms 1052 KB
large/31_large60 AC 22 ms 952 KB
large/31_large61 AC 25 ms 1076 KB
large/31_large62 AC 24 ms 1292 KB
large/31_large63 AC 22 ms 1048 KB
large/31_large64 AC 22 ms 824 KB
large/31_large65 AC 21 ms 1068 KB
large/31_large66 AC 23 ms 788 KB
large/31_large67 AC 22 ms 1168 KB
large/31_large68 AC 22 ms 908 KB
large/31_large69 AC 24 ms 820 KB
large/32_large70 AC 114 ms 1212 KB
large/32_large71 AC 82 ms 1204 KB
large/32_large72 AC 165 ms 1196 KB
large/32_large73 AC 117 ms 1204 KB
large/32_large74 AC 585 ms 1412 KB
large/32_large75 AC 154 ms 1332 KB
large/32_large76 AC 465 ms 1324 KB
large/32_large77 AC 339 ms 1336 KB
large/32_large78 AC 90 ms 1332 KB
large/32_large79 AC 151 ms 1332 KB
large/33_large80 AC 30 ms 1204 KB
medium/20_manual5 AC 20 ms 692 KB
medium/20_manual6 AC 21 ms 792 KB
medium/21_medium30 AC 22 ms 788 KB
medium/21_medium31 AC 21 ms 672 KB
medium/21_medium32 AC 20 ms 784 KB
medium/21_medium33 AC 21 ms 696 KB
medium/21_medium34 AC 20 ms 788 KB
medium/21_medium35 AC 20 ms 700 KB
medium/21_medium36 AC 21 ms 780 KB
medium/21_medium37 AC 21 ms 696 KB
medium/21_medium38 AC 21 ms 692 KB
medium/21_medium39 AC 21 ms 788 KB
medium/21_medium40 AC 20 ms 788 KB
medium/21_medium41 AC 21 ms 784 KB
medium/21_medium42 AC 19 ms 788 KB
medium/21_medium43 AC 21 ms 792 KB
medium/21_medium44 AC 19 ms 788 KB
medium/21_medium45 AC 21 ms 792 KB
medium/21_medium46 AC 22 ms 780 KB
medium/21_medium47 AC 20 ms 788 KB
medium/21_medium48 AC 20 ms 788 KB
medium/21_medium49 AC 20 ms 784 KB
medium/21_medium50 AC 20 ms 796 KB
medium/21_medium51 AC 21 ms 664 KB
medium/21_medium52 AC 22 ms 788 KB
medium/21_medium53 AC 21 ms 692 KB
medium/21_medium54 AC 22 ms 784 KB
medium/21_medium55 AC 20 ms 788 KB
medium/21_medium56 AC 21 ms 820 KB
medium/21_medium57 AC 20 ms 656 KB
medium/21_medium58 AC 20 ms 780 KB
medium/21_medium59 AC 19 ms 788 KB
small/01_manual1 AC 21 ms 688 KB
small/01_manual2 AC 20 ms 664 KB
small/01_sample2 AC 24 ms 668 KB
small/10_manual3 AC 21 ms 788 KB
small/11_small00 AC 21 ms 784 KB
small/11_small01 AC 22 ms 696 KB
small/11_small02 AC 20 ms 692 KB
small/11_small03 AC 20 ms 780 KB
small/11_small04 AC 21 ms 784 KB
small/11_small05 AC 19 ms 788 KB
small/11_small06 AC 20 ms 788 KB
small/11_small07 AC 21 ms 784 KB
small/11_small08 AC 20 ms 792 KB
small/11_small09 AC 20 ms 816 KB
small/11_small10 AC 20 ms 660 KB
small/11_small11 AC 20 ms 692 KB
small/11_small12 AC 20 ms 688 KB
small/11_small13 AC 22 ms 788 KB
small/11_small14 AC 20 ms 792 KB
small/11_small15 AC 20 ms 796 KB
small/11_small16 AC 20 ms 792 KB
small/11_small17 AC 21 ms 784 KB
small/11_small18 AC 20 ms 772 KB
small/11_small19 AC 21 ms 808 KB
small/11_small20 AC 19 ms 788 KB
small/11_small21 AC 20 ms 788 KB
small/11_small22 AC 20 ms 792 KB
small/11_small23 AC 20 ms 804 KB
small/11_small24 AC 20 ms 792 KB
small/11_small25 AC 21 ms 788 KB
small/11_small26 AC 20 ms 784 KB
small/11_small27 AC 21 ms 808 KB
small/11_small28 AC 21 ms 788 KB
small/11_small29 AC 20 ms 788 KB