Submission #6694843


Source Code Expand

Copy
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/stack:200000000")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
 
#define X first
#define Y second
 
//#include <boost/unordered_map.hpp>
//using namespace boost;
 
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/
 
using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
//using i128 = __int128_t;
//using u128 = __uint128_t;
using i128 = i64;
using u128 = u64;
 
ll power(ll a, ll b, ll p)
{
    if (!b) return 1;
    ll t = power(a, b/2, p);
    t = t*t%p;
    if (b&1) t = t*a%p;
    return t;
}
 
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll px, py;
    ll d = exgcd(b, a%b, px, py);
    x = py;
    y = px-a/b*py;
    return d;
}
 
template<class T>
inline void freshmin(T &a, const T &b)
{
    if (a > b) a = b;
}
 
template<class T>
inline void freshmax(T &a, const T &b)
{
    if (a < b) a = b;
}
 
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
 
int inp() {
    int x = 0, f = 0; char ch;
    for(ch = getchar(); !isdigit(ch); ch = getchar())
        if(ch == '-') f = 1;
    for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    return f ? -x : x;
}
 
ll inp_ll() {
    ll x = 0; int f = 0; char ch;
    for(ch = getchar(); !isdigit(ch); ch = getchar())
        if(ch == '-') f = 1;
    for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    return f ? -x : x;
}
 
template<class T>
bool read(T &x)
{
    x = 0;
    char ch = getchar();
    if (ch == EOF) return 0;
    for(; !isdigit(ch); )
    {
        ch = getchar();
        if (ch == EOF) return 0;
    }
    for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    return 1;
}
 
template<class T>
void write(T x)
{
    static char s[22];
    static char *it = s+20;
    static char *end = s+20;
    if (!x)
        *-- it = '0';
    while (x)
    {
        *-- it = x%10+'0';
        x /= 10;
    }
    for (; it < end; ++ it)
        putchar(*it);
}
 
template<class T>
void writeln(T x)
{
    write(x);
    putchar('\n');
}
 
const int MAXN = 200010;
const int INF = 1000000000;
const int MOD = 1000000007;

int n;
char s[MAXN];
int u[MAXN], a[MAXN], to[MAXN];
pii f[MAXN];

void dfs(int x)
{
	if (to[to[x]] == x)
		f[x] = {x, to[x]};
	else
	{
		if (!u[to[x]])
		{
			u[to[x]] = 1;
			dfs(to[x]);
		}
		f[x] = f[to[x]];
		swap(f[x].X, f[x].Y);
	}
}

int main()
{
	
	scanf("%s", s+1);
	n = strlen(s+1);
	for (int i = 1; i <= n; ++ i)
	{
		int j = i;
		if (s[i] == 'L') j --; else j ++;
		to[i] = j;
	}
	for (int i = 1; i <= n; ++ i)
	{
		if (!u[i]) dfs(i);
		a[f[i].X] ++;
	}
	for (int i = 1; i <= n; ++ i)
		printf("%d ", a[i]);
	
	return 0;
}

Submission Info

Submission Time
Task D - Gathering Children
User liouzhou_101
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3429 Byte
Status AC
Exec Time 12 ms
Memory 5248 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:164:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s+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 2 ms 2304 KB
sample_02 AC 2 ms 2304 KB
sample_03 AC 2 ms 2304 KB
testcase_01 AC 8 ms 3200 KB
testcase_02 AC 7 ms 3072 KB
testcase_03 AC 11 ms 3712 KB
testcase_04 AC 11 ms 3712 KB
testcase_05 AC 8 ms 3200 KB
testcase_06 AC 9 ms 3456 KB
testcase_07 AC 11 ms 3712 KB
testcase_08 AC 11 ms 3712 KB
testcase_09 AC 4 ms 2816 KB
testcase_10 AC 11 ms 4096 KB
testcase_11 AC 10 ms 3712 KB
testcase_12 AC 11 ms 3712 KB
testcase_13 AC 11 ms 3712 KB
testcase_14 AC 12 ms 5248 KB
testcase_15 AC 12 ms 5248 KB
testcase_16 AC 10 ms 3712 KB
testcase_17 AC 11 ms 3712 KB
testcase_18 AC 2 ms 2304 KB