제출 #416995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
416995		Collypso	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	34 / 100	1095 ms	146144 KiB

scrivener

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#define F first
#define S second
//#define endl '\n'
//#define int long long

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

using namespace std;

const int const_lg = 20;

struct node
{
    char val;
    int h;
    vt<int> children, parent;

    node() { }

    node(char val_, int parent_, int h_)
    {
        val = val_, h = h_;
        parent.pb(parent_);
    }
};

vt<node> trie;
vt<int> commands;

void Init()
{
    trie.pb({'#', 0, -1});
    commands.pb(0);
}

void TypeLetter(char L)
{
    int i = *commands.rbegin();
    trie[i].children.pb(sz(trie));
    trie.pb({L, i, trie[i].h + 1});
    for(int i = 1, v = sz(trie) - 1; trie[trie[v].parent[i - 1]].val != '#'; i++)
    {
        //cout << v << " " << i << " " << trie[trie[v].parent[i - 1]].parent.size() << endl;
        if (trie[trie[v].parent[i - 1]].parent.size() <= i) trie[v].parent.pb(0);
        else trie[v].parent.pb(trie[trie[v].parent[i - 1]].parent[i - 1]);
        //cout << "ok" << endl;

        //for(int i : trie[v].parent) cout << i << " ";
        //cout << endl;
    }
    //cout << "***" << endl;
    commands.pb(sz(trie) - 1);
}

void UndoCommands(int U)
{
    int n = sz(commands);
    commands.pb(commands[n - U - 1]);
}

char GetLetter(int P)
{
    int v = *commands.rbegin();
    for(int k = sz(trie[v].parent) - 1; k >= 0; k = min(k - 1, sz(trie[v].parent) - 1))
        if (trie[trie[v].parent[k]].h >= P ) v = trie[v].parent[k];
    return trie[v].val;
}

컴파일 시 표준 에러 (stderr) 메시지

scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:56:55: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |         if (trie[trie[v].parent[i - 1]].parent.size() <= i) trie[v].parent.pb(0);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40