oj.uz

답안 #138840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138840 2019-07-30T12:56:20 Z MrBrionix 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 793 ms 95376 KB 
#include<bits/stdc++.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
using namespace std;

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

int siz[1000005],succ[1000005][22],cont;
char c[1000005];

void Init(){
    
    siz[0]=0;
    for(int i=0;i<1000005;i++)for(int j=0;j<22;j++)succ[i][j]=-1;
    cont=1;
    succ[0][0]=0;
    return;
}


void TypeLetter(char L){
    
    c[cont]=L;
    siz[cont]=siz[cont-1]+1;
    
    succ[cont][0]=cont;
    succ[cont][1]=succ[cont-1][0];
    
    for(int i=2;i<22;i++){
        if(succ[cont][i-1]!=-1)
        succ[cont][i]=succ[succ[cont][i-1]][i-1];
        else break;
    }
    
    cont++;
}


void UndoCommands(int U){
    
    siz[cont]=siz[cont-1-U];
    for(int i=0;i<22;i++){
        if(succ[cont-1-U][i]!=-1)
        succ[cont][i]=succ[cont-1-U][i];
        else break;
    }
    
    cont++;
}

char GetLetter(int P){
    
    int num=siz[cont-1]-1-P,pos=cont-1;

    for(int j=21;j>=1;j--){
        if((1ll<<(j-1ll))<=num){
            num-=(1ll<<(j-1ll));
            pos=succ[pos][j];
        }
        if(num==0)break;
    }
    
    /*
    cout<<"debug"<<endl;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            cout<<succ[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"-------------"<<endl;
    */
    
    return c[succ[pos][0]];
}

/*

int main() {
  Init();

  int cmd_num,tmp;
  tmp = scanf("%d", &cmd_num);
  assert(tmp == 1);

  int i;
  for (i = 0; i < cmd_num; i++) {
    char cmd;
    tmp = scanf(" %c", &cmd);
    assert(tmp == 1);
    if (cmd == 'T') {
      char letter;
      tmp = scanf(" %c", &letter);
      assert(tmp == 1);
      TypeLetter(letter);
    }
    else if (cmd == 'U') {
      int number;
      tmp = scanf("%d", &number);
      assert(tmp == 1);
      UndoCommands(number);
    }
    else if (cmd == 'P') {
      int index;
      char letter;
      tmp = scanf("%d", &index);
      assert(tmp == 1);
      letter = GetLetter(index);
      printf("%c\n", letter);
    }
  }
  
  puts("Let's test for cheating!!");

  return 0;

}*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 86392 KB Output is correct
2 Correct 86 ms 86492 KB Output is correct
3 Correct 86 ms 86392 KB Output is correct
4 Correct 97 ms 86500 KB Output is correct
5 Correct 86 ms 86392 KB Output is correct
6 Correct 85 ms 86392 KB Output is correct
7 Correct 90 ms 86520 KB Output is correct
8 Correct 86 ms 86520 KB Output is correct
9 Correct 86 ms 86520 KB Output is correct
10 Correct 85 ms 86520 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 86436 KB Output is correct
2 Correct 87 ms 86416 KB Output is correct
3 Correct 102 ms 86608 KB Output is correct
4 Correct 103 ms 86480 KB Output is correct
5 Correct 90 ms 86356 KB Output is correct
6 Correct 88 ms 86520 KB Output is correct
7 Correct 93 ms 86520 KB Output is correct
8 Correct 90 ms 86520 KB Output is correct
9 Correct 86 ms 86520 KB Output is correct
10 Correct 87 ms 86520 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 86392 KB Output is correct
2 Correct 87 ms 86648 KB Output is correct
3 Correct 88 ms 86520 KB Output is correct
4 Correct 88 ms 86524 KB Output is correct
5 Correct 88 ms 86520 KB Output is correct
6 Correct 91 ms 86520 KB Output is correct
7 Correct 87 ms 86520 KB Output is correct
8 Correct 87 ms 86648 KB Output is correct
9 Correct 88 ms 86520 KB Output is correct
10 Correct 88 ms 86520 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 542 ms 90544 KB Output is correct
2 Correct 616 ms 91128 KB Output is correct
3 Correct 495 ms 91280 KB Output is correct
4 Correct 503 ms 91616 KB Output is correct
5 Correct 521 ms 91128 KB Output is correct
6 Correct 442 ms 91588 KB Output is correct
7 Correct 618 ms 91244 KB Output is correct
8 Correct 603 ms 91684 KB Output is correct
9 Correct 619 ms 91644 KB Output is correct
10 Correct 268 ms 92020 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 678 ms 90812 KB Output is correct
2 Correct 793 ms 90648 KB Output is correct
3 Correct 432 ms 91084 KB Output is correct
4 Correct 457 ms 91020 KB Output is correct
5 Correct 458 ms 91556 KB Output is correct
6 Correct 455 ms 91716 KB Output is correct
7 Correct 477 ms 91616 KB Output is correct
8 Correct 755 ms 91256 KB Output is correct
9 Correct 778 ms 91084 KB Output is correct
10 Correct 275 ms 95376 KB Output is correct