oj.uz

Submission #17745

# Submission time Handle Problem Language Result Execution time Memory
17745 2016-01-12T09:55:06 Z chrome Energetic turtle (IZhO11_turtle) C++
15 / 100
 1252 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define foreach(it, S) for (__typeof (S.begin()) it = S.begin(); it != S.end(); it++)
#define all(x) x.begin(), x.end()
#define endl '\n'
#define _ ios_base :: sync_with_stdio(false); cin.tie(NULL);

#ifdef inputf
	#define fname ""
#else
	#define fname "" // <- Here
#endif

const double eps = 1e-9;
const int MaxN = int(2e5) + 256;
const int MOD = int(1e9) + 7;

template <typename T> inline T gcd(T a, T b) {
	return b ? gcd (b, a % b) : a;
}

inline bool Palindrome(const string& s) {
	return equal(s.begin(), s.end(), s.rbegin());
}

int d[21][1200][1200];
int f[10 * MaxN], inv[10 * MaxN];
int a[1200][1200];
int c[5000][5000];

inline int binpow(int a, int n, int z) {
	int res = 1;
	while (n) {
		if (n & 1)
			res = (res * 1ll * a) % z;
		a = (a * 1ll * a) % z;
		n >>= 1;
	}
	return res;
}

inline int get(int n, int k, int z) {
	return f[n] * inv[k] % z * inv[n - k] % z; 
}

inline bool prime(int v) {
	if (~v & 1) return false;
	for (int i = 3; i * i <= v; i += 2)
		if (v % i == 0)
			return false;
	return true;
}

int main() { // _
	#ifdef lcl
		freopen(fname".in", "r", stdin);
		freopen(fname".out", "w", stdout);
	#endif

	int n, m, k, t, z; scanf("%d%d%d%d%d", &n, &m, &k, &t, &z);

	for (int i = 0; i < k; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		a[x][y] = 1;
	}

	f[0] = inv[0] = 1;
	
	for (int i = 1; i <= n + m; ++i) {
		f[i] = f[i - 1] * 1ll * i % z;
		inv[i] = binpow(f[i], z - 2, z);
	}
	
	if (prime(z)) {
		cout << get(n + m, n, z);
	} else {
		for (int i = 1; i <= n + m; ++i) {
			c[i][0] = c[i][i] = 1;
			for (int j = 1; j < i; ++j) {
				c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % z;
			}
		}
		cout << c[n + m][n];
	}
	
	return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:63:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m, k, t, z; scanf("%d%d%d%d%d", &n, &m, &k, &t, &z);
                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 3 ms 376 KB Output isn't correct
7 Incorrect 3 ms 500 KB Output isn't correct
8 Incorrect 3 ms 380 KB Output isn't correct
9 Incorrect 7 ms 504 KB Output isn't correct
10 Incorrect 11 ms 632 KB Output isn't correct
11 Runtime error 14 ms 452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 272 ms 5112 KB Output isn't correct
13 Runtime error 15 ms 608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 926 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 16 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 14 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 15 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 15 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 1252 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 15 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)