oj.uz

Submission #72363

# Submission time Handle Problem Language Result Execution time Memory
72363 2018-08-26T07:28:38 Z RR rangers(#2172, jwvg0425, ozt88, choy907) Dstorv (FXCUP3_dstorv) C++17
0 / 100
 4 ms 872 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <sstream>
#include <iterator>
#define MOD ((i64)(1e9+7))

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

// table[r][h] = R이 r개, H가 h개 있을 때 둘다 0개가 될 확률
ii64 table[5001][5001];

i64 ipow(i64 x, i64 k)
{
	if (k == 0)
		return 1;

	i64 half = ipow(x, k / 2);

	half = (half * half) % MOD;

	if (k % 2 == 0)
		return half;
	else
		return (half * x) % MOD;
}

int main()
{
	int n, r, h;
	scanf("%d %d %d", &n, &r, &h);

	string s;

	cin >> s;

	table[0][0].first = table[0][0].second = 1;

	ii64 flowerp, handp;

	flowerp.first = h;
	flowerp.second = r + h;

	handp.first = r;
	handp.second = r + h;

	for(int flower = 0; flower <= n; flower ++)
	{
		for(int hand = 0; hand <= n; hand++)
		{
			if (flower == 0 && hand == 0)
				continue;

			table[flower][hand].first = 0;
			table[flower][hand].second = 1;
			
			if (flower > 0)
			{
				table[flower][hand].first = (handp.first * table[flower - 1][hand].first) % MOD;
				table[flower][hand].second = (handp.second * table[flower - 1][hand].second) % MOD;
			}

			if (hand > 0)
			{
				ii64 f(flowerp.first * table[flower][hand - 1].first % MOD, flowerp.second * table[flower][hand - 1].second % MOD);

				table[flower][hand].first =
					(table[flower][hand].first * f.second + table[flower][hand].second * f.first) % MOD;

				table[flower][hand].second = (table[flower][hand].second * f.second) % MOD;
			}
		}
	}

	int a, b;
	scanf("%d %d", &a, &b);

	ii64 ans(0, 1);
	for (int i = 0; i < s.size() - 1; i++)
	{
		if (s[i] != 'H' || s[i + 1] != 'R')
			continue;

		int leftmost = -1;
		for (int j = 0; j <= i; j++)
		{
			if (s[j] == 'R')
			{
				leftmost = j;
				break;
			}
		}

		ii64 leftp = ii64(1,1);
		int hl = 0, hr = 0;
		int remainr = 0;

		for (int j = 0; j <= i; j++)
		{
			if (s[j] != 'H')
			{
				remainr++;
				continue;
			}

			if (j <= leftmost)
				hl++;
			else
				hr++;
		}

		if (leftmost == -1)
		{
			if (hl != b)
				continue;
		}
		else
		{
			int remain = b - hl;

			if (remain < 0)
				continue;

			int need = hr - remain;

			if (need == hr)
				continue;

			leftp = table[remainr][need];
		}

		ii64 rightp(1,1);

		int rightmost = -1;
		for (int j = n - 1; j > i; j--)
		{
			if (s[j] == 'H')
			{
				rightmost = j;
				break;
			}
		}

		int rl = 0, rr = 0;
		int remainh = 0;

		for (int j = n - 1; j > i ; j--)
		{
			if (s[j] != 'R')
			{
				remainh++;
				continue;
			}

			if (j >= rightmost)
				rr++;
			else
				rl++;
		}

		if (rightmost == -1)
		{
			if (rr != a)
				continue;
		}
		else
		{
			int remain = a - rr;

			if (remain < 0)
				continue;

			int need = rl - remain;

			if (need == rl)
				continue;

			rightp = table[need][remainh];
		}

		ii64 p(leftp.first * rightp.first % MOD, leftp.second * rightp.second % MOD);

		ans.first = ((ans.first * p.second) %MOD + (ans.second * p.first) % MOD) %MOD;
		ans.second = (ans.second * p.second) % MOD;
	}

	printf("%lld\n", (ans.first * ipow(ans.second, MOD - 2) % MOD));

	return 0;
}

Compilation message

dstorv.cpp: In function 'int main()':
dstorv.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size() - 1; i++)
                  ~~^~~~~~~~~~~~~~
dstorv.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &r, &h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dstorv.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -