Submission #6694678


Source Code Expand

Copy
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define Fast_cin ios::sync_with_stdio(false), cin.tie(0);
#define rep(i, a, b) for(register int i = a; i <= b; i++)
#define per(i, a, b) for(register int i = a; i >= b; i--)
using namespace std;

typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;

template <typename _T>
inline void read(_T &f) {
    f = 0; _T fu = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') fu = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

template <typename T>
struct hash_map_t {
    vector <T> v, val, nxt;
    vector <int> head;
    int mod, tot, lastv;
    T lastans;
    bool have_ans;

    hash_map_t (int md = 0) {
        head.clear(); v.clear(); val.clear(); nxt.clear(); tot = 0; mod = md;
        nxt.resize(1); v.resize(1); val.resize(1); head.resize(mod);
        have_ans = 0;
    }

    void clear() { *this = hash_map_t(mod); }

    bool count(int x) {
        int u = x % mod;
        for(register int i = head[u]; i; i = nxt[i]) {
            if(v[i] == x) {
                have_ans = 1;
                lastv = x;
                lastans = val[i];
                return 1;
            }
        }
        return 0;
    }

    void ins(int x, int y) {
        int u = x % mod;
        nxt.push_back(head[u]); head[u] = ++tot;
        v.push_back(x); val.push_back(y);
    }

    int qry(int x) {
        if(have_ans && lastv == x) return lastans;
        count(x);
        return lastans;
    }
};

const int N = 1e5 + 5;

char c[N];
int f[N][400], g[400], now[400], ans[N];
int n;

void gen_g() {
    now[101] = 1; int len = 101, cnt = 0;
    while(len) {
        g[++cnt] = now[1] & 1;
        for(register int i = len; i >= 1; i--) {
            if(now[i] & 1) now[i - 1] += 10;
            now[i] >>= 1;
        }
        while(len && !now[len]) --len;
    }
}

int main() {
    scanf("%s", c + 1); n = strlen(c + 1);
    for(register int i = 1; i <= n; i++) f[i][0] = i + (c[i] == 'L' ? -1 : 1);
    for(register int j = 1; j < 400; j++) {
        for(register int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    gen_g();
    for(register int i = 1; i <= n; i++) {
        int now = i;
        for(register int j = 0; j < 400; j++) {
            if(g[j]) {
                now = f[now][j];
            }
        }
        ++ans[now];
    }
    for(register int i = 1; i <= n; i++) print(ans[i], i == n ? '\n' : ' ');
    return 0;
}

Submission Info

Submission Time
Task D - Gathering Children
User LJC00118
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2921 Byte
Status AC
Exec Time 240 ms
Memory 157184 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", c + 1); n = strlen(c + 1);
                       ^

Judge Result

Set Name All Sample
Score / Max Score 400 / 400 0 / 0
Status
AC × 21
AC × 3
Set Name Test Cases
All sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18
Sample sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 1 ms 256 KB
testcase_01 AC 150 ms 100608 KB
testcase_02 AC 141 ms 94464 KB
testcase_03 AC 240 ms 157184 KB
testcase_04 AC 240 ms 157184 KB
testcase_05 AC 148 ms 102528 KB
testcase_06 AC 190 ms 131456 KB
testcase_07 AC 231 ms 157184 KB
testcase_08 AC 232 ms 157184 KB
testcase_09 AC 51 ms 36736 KB
testcase_10 AC 232 ms 156800 KB
testcase_11 AC 231 ms 157184 KB
testcase_12 AC 230 ms 156416 KB
testcase_13 AC 231 ms 156928 KB
testcase_14 AC 233 ms 156800 KB
testcase_15 AC 232 ms 156800 KB
testcase_16 AC 232 ms 156800 KB
testcase_17 AC 232 ms 156800 KB
testcase_18 AC 1 ms 256 KB