oj.uz

Submission #140164

# Submission time Handle Problem Language Result Execution time Memory
140164 2019-08-02T08:05:27 Z rdd6584 Fully Generate (KRIII5_FG) C++14
2 / 7
 500 ms 78528 KB 
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

int vec[20000001];

ll mp(ll a, ll b) {
	ll ret = 1;
	while (b) {
		if (b % 2) ret = ret * a % MOD;
		a = a * a % MOD;
		b /= 2;
	}

	return ret;
}

int main() {
	ll n;
	scanf("%lld", &n);

	if (n == 1) return !printf("1");
	if (n == 2) return !printf("2");
	if (n == 3) return !printf("4");

	int now = 3; // 수 이자 인덱스.
	ll cnt = 3; // 여태까지 이만큼 쌓음.
	ll ans = 4;
	vec[1] = 1, vec[2] = 2, vec[3] = 2;

	while (1) {
		if (vec[now] + cnt >= n) {
			ans = ans * mp(now, n - cnt) % MOD;
			break;
		}

		for (ll i = cnt + 1; i <= vec[now] + cnt && i <= 20000000; i++)
			vec[i] = now;

		// printf("%d : %d %lld %lld\n", now, vec[now], cnt + 1, cnt + vec[now]);

		ans = ans * mp(now, vec[now]) % MOD;
		cnt += vec[now];
		now++;
	}

	printf("%lld", ans);
}

Compilation message

FG.cpp: In function 'int main()':
FG.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 3 ms 892 KB Output is correct
12 Correct 6 ms 3832 KB Output is correct
13 Correct 5 ms 2808 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 5 ms 3448 KB Output is correct
16 Correct 4 ms 2552 KB Output is correct
17 Correct 3 ms 1532 KB Output is correct
18 Correct 5 ms 3064 KB Output is correct
19 Correct 3 ms 760 KB Output is correct
20 Correct 4 ms 1272 KB Output is correct
21 Correct 5 ms 2808 KB Output is correct
22 Correct 4 ms 1784 KB Output is correct
23 Correct 3 ms 888 KB Output is correct
24 Correct 6 ms 3832 KB Output is correct
25 Correct 3 ms 1400 KB Output is correct
26 Correct 2 ms 504 KB Output is correct
27 Correct 5 ms 3448 KB Output is correct
28 Correct 4 ms 1144 KB Output is correct
29 Correct 6 ms 4088 KB Output is correct
30 Correct 3 ms 1656 KB Output is correct
31 Correct 5 ms 2936 KB Output is correct
32 Correct 3 ms 892 KB Output is correct
33 Correct 6 ms 3576 KB Output is correct
34 Correct 4 ms 1528 KB Output is correct
35 Correct 5 ms 3704 KB Output is correct
36 Correct 3 ms 1656 KB Output is correct
37 Correct 3 ms 760 KB Output is correct
38 Correct 4 ms 2172 KB Output is correct
39 Correct 5 ms 3704 KB Output is correct
40 Correct 5 ms 2936 KB Output is correct
41 Correct 3 ms 888 KB Output is correct
42 Correct 5 ms 2936 KB Output is correct
43 Correct 3 ms 888 KB Output is correct
44 Correct 5 ms 3576 KB Output is correct
45 Correct 3 ms 1528 KB Output is correct
46 Correct 5 ms 3704 KB Output is correct
47 Correct 3 ms 1656 KB Output is correct
48 Correct 5 ms 3704 KB Output is correct
49 Correct 4 ms 2296 KB Output is correct
50 Correct 6 ms 4216 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 3 ms 892 KB Output is correct
12 Correct 6 ms 3832 KB Output is correct
13 Correct 5 ms 2808 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 5 ms 3448 KB Output is correct
16 Correct 4 ms 2552 KB Output is correct
17 Correct 3 ms 1532 KB Output is correct
18 Correct 5 ms 3064 KB Output is correct
19 Correct 3 ms 760 KB Output is correct
20 Correct 4 ms 1272 KB Output is correct
21 Correct 5 ms 2808 KB Output is correct
22 Correct 4 ms 1784 KB Output is correct
23 Correct 3 ms 888 KB Output is correct
24 Correct 6 ms 3832 KB Output is correct
25 Correct 3 ms 1400 KB Output is correct
26 Correct 2 ms 504 KB Output is correct
27 Correct 5 ms 3448 KB Output is correct
28 Correct 4 ms 1144 KB Output is correct
29 Correct 6 ms 4088 KB Output is correct
30 Correct 3 ms 1656 KB Output is correct
31 Correct 5 ms 2936 KB Output is correct
32 Correct 3 ms 892 KB Output is correct
33 Correct 6 ms 3576 KB Output is correct
34 Correct 4 ms 1528 KB Output is correct
35 Correct 5 ms 3704 KB Output is correct
36 Correct 3 ms 1656 KB Output is correct
37 Correct 3 ms 760 KB Output is correct
38 Correct 4 ms 2172 KB Output is correct
39 Correct 5 ms 3704 KB Output is correct
40 Correct 5 ms 2936 KB Output is correct
41 Correct 3 ms 888 KB Output is correct
42 Correct 5 ms 2936 KB Output is correct
43 Correct 3 ms 888 KB Output is correct
44 Correct 5 ms 3576 KB Output is correct
45 Correct 3 ms 1528 KB Output is correct
46 Correct 5 ms 3704 KB Output is correct
47 Correct 3 ms 1656 KB Output is correct
48 Correct 5 ms 3704 KB Output is correct
49 Correct 4 ms 2296 KB Output is correct
50 Correct 6 ms 4216 KB Output is correct
51 Execution timed out 1084 ms 78528 KB Time limit exceeded
52 Halted 0 ms 0 KB -