oj.uz

Submission #137991

# Submission time Handle Problem Language Result Execution time Memory
137991 2019-07-28T17:52:10 Z sebinkim Remittance (JOI19_remittance) C++14
15 / 100
 3 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll A[1010101], B[1010101], X[1010101];
ll n, p, q, s, a, b, x, t;

void die() { printf("No\n"); exit(0); }

ll pow(ll a, ll b)
{
	ll ret = 1;
	
	for(; b; b>>=1){
		if(b & 1) ret = ret * a % mod;
		a = a * a % mod;
	}
	
	return ret;
}

void check()
{
	ll i, j;
	
	p = (pow(2ll, n) - 1 + mod) % mod;
	q = pow(p, mod - 2);
	s = 0; x = 0; t = 0;
	
	for(i=n; i>=1; i--){
		s = (s * 2 + (A[i] - B[i]) + mod) % mod;
	}
	
	X[n] = s * q % mod;
	
	for(i=n-1; i>=1; i--){
		s = (s * 2 - (A[i + 1] - B[i + 1]) * p % mod + mod) % mod;
		X[i] = s * q % mod;
	}
		
	X[0] = X[n];
	
	for(i=1; i<=n; i++){
		x += X[i];
		if(X[i] < 0) die();
		if(A[i] + X[i - 1] - X[i] * 2 != B[i]) die();
	}
	
	if(a - b != x) die();
	
	for(j=1; j<=2; j++){
		for(i=1; i<=n; i++){
			if(A[i] >= X[i] * 2){
				A[i % n + 1] += X[i];
				A[i] -= X[i] * 2;
				X[i] = 0;
			}
			else{
				A[i % n + 1] += A[i] / 2;
				X[i] -= A[i] / 2;
				A[i] -= A[i] / 2 * 2;
			}
		}
	}
	
	for(i=1; i<=n; i++){
		if(A[i] != B[i]) die();
	}
}

int main()
{
	ll i;
	
	scanf("%lld", &n);
	
	for(i=1; i<=n; i++){
		scanf("%lld%lld", A + i, B + i);
		a += A[i]; b += B[i];
	}
	
	if(a < b) die();
	
	check();
	
	printf("Yes\n");
	
	return 0;
}

Compilation message

remittance.cpp: In function 'int main()':
remittance.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
remittance.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", A + i, B + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 380 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 504 KB Output is correct
32 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 380 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 504 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 3 ms 376 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 348 KB Output is correct
41 Correct 2 ms 248 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 376 KB Output is correct
44 Correct 2 ms 376 KB Output is correct
45 Correct 2 ms 376 KB Output is correct
46 Correct 2 ms 376 KB Output is correct
47 Correct 2 ms 380 KB Output is correct
48 Correct 2 ms 376 KB Output is correct
49 Correct 2 ms 376 KB Output is correct
50 Correct 2 ms 376 KB Output is correct
51 Correct 2 ms 380 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 3 ms 376 KB Output is correct
54 Incorrect 2 ms 376 KB Output isn't correct
55 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 380 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 504 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 3 ms 376 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 348 KB Output is correct
41 Correct 2 ms 248 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 376 KB Output is correct
44 Correct 2 ms 376 KB Output is correct
45 Correct 2 ms 376 KB Output is correct
46 Correct 2 ms 376 KB Output is correct
47 Correct 2 ms 380 KB Output is correct
48 Correct 2 ms 376 KB Output is correct
49 Correct 2 ms 376 KB Output is correct
50 Correct 2 ms 376 KB Output is correct
51 Correct 2 ms 380 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 3 ms 376 KB Output is correct
54 Incorrect 2 ms 376 KB Output isn't correct
55 Halted 0 ms 0 KB -