oj.uz

Submission #58488

# Submission time Handle Problem Language Result Execution time Memory
58488 2018-07-18T03:06:22 Z E869120 Horses (IOI15_horses) C++14
54 / 100
 1500 ms 133556 KB 
#include "horses.h"
#include <iostream>
using namespace std;

long long N, X[500009], Y[500009], Allval = 0, mod = 1000000007;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 31; i++) {
		if ((b&(1LL << i)) != 0) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long Div(long long a, long long b, long long m) {
	return (1LL * a*modpow(b, m - 2, m)) % m;
}

int solve() {
	pair<int, int>maxid = make_pair(0, 1);

	long long P = 1;
	for (int i = N - 1; i >= 0; i--) {
		// Y[i] / P と比べる
		if (maxid.first*P < maxid.second * Y[i]) maxid = make_pair(Y[i], P);
		P *= X[i]; if (P >= (1LL << 30)) break;
	}
	long long J = Div(Allval, maxid.second, mod);
	J *= maxid.first; J %= mod;
	return J;
}

int init(int NN, int XX[], int YY[]) {
	N = NN; Allval = 1;
	for (int i = 0; i < N; i++) { X[i] = XX[i]; Allval *= X[i]; Allval %= mod; }
	for (int i = 0; i < N; i++) Y[i] = YY[i];
	return solve();
}

int updateX(int pos, int val) {	
	Allval = Div(Allval, X[pos], mod);
	X[pos] = val;
	Allval *= X[pos]; Allval %= mod;
	return solve();
}

int updateY(int pos, int val) {
	Y[pos] = val;
	return solve();
}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:24:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  for (int i = N - 1; i >= 0; i--) {
               ~~^~~
horses.cpp:31:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return J;
         ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 528 KB Output is correct
7 Correct 2 ms 528 KB Output is correct
8 Correct 2 ms 528 KB Output is correct
9 Correct 3 ms 628 KB Output is correct
10 Correct 2 ms 628 KB Output is correct
11 Correct 2 ms 648 KB Output is correct
12 Correct 2 ms 648 KB Output is correct
13 Correct 3 ms 648 KB Output is correct
14 Correct 3 ms 648 KB Output is correct
15 Correct 2 ms 712 KB Output is correct
16 Correct 3 ms 712 KB Output is correct
17 Correct 2 ms 712 KB Output is correct
18 Correct 2 ms 712 KB Output is correct
19 Correct 2 ms 712 KB Output is correct
20 Correct 3 ms 712 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 15036 KB Output is correct
2 Correct 250 ms 27756 KB Output is correct
3 Correct 224 ms 31480 KB Output is correct
4 Correct 243 ms 39280 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 39280 KB Output is correct
2 Correct 2 ms 39280 KB Output is correct
3 Correct 2 ms 39280 KB Output is correct
4 Correct 2 ms 39280 KB Output is correct
5 Correct 2 ms 39280 KB Output is correct
6 Correct 2 ms 39280 KB Output is correct
7 Correct 2 ms 39280 KB Output is correct
8 Correct 2 ms 39280 KB Output is correct
9 Correct 2 ms 39280 KB Output is correct
10 Correct 3 ms 39280 KB Output is correct
11 Correct 2 ms 39280 KB Output is correct
12 Correct 3 ms 39280 KB Output is correct
13 Correct 2 ms 39280 KB Output is correct
14 Correct 3 ms 39280 KB Output is correct
15 Correct 3 ms 39280 KB Output is correct
16 Correct 2 ms 39280 KB Output is correct
17 Correct 2 ms 39280 KB Output is correct
18 Correct 3 ms 39280 KB Output is correct
19 Correct 3 ms 39280 KB Output is correct
20 Correct 2 ms 39280 KB Output is correct
21 Correct 3 ms 39280 KB Output is correct
22 Correct 3 ms 39280 KB Output is correct
23 Correct 4 ms 39280 KB Output is correct
24 Correct 4 ms 39280 KB Output is correct
25 Correct 3 ms 39280 KB Output is correct
26 Correct 4 ms 39280 KB Output is correct
27 Correct 4 ms 39280 KB Output is correct
28 Correct 4 ms 39280 KB Output is correct
29 Correct 6 ms 39280 KB Output is correct
30 Correct 6 ms 39280 KB Output is correct
31 Correct 6 ms 39280 KB Output is correct
32 Correct 5 ms 39280 KB Output is correct
33 Correct 108 ms 39280 KB Output is correct
34 Correct 49 ms 42224 KB Output is correct
35 Correct 90 ms 53024 KB Output is correct
36 Correct 95 ms 63956 KB Output is correct
37 Correct 408 ms 66024 KB Output is correct
38 Correct 56 ms 69048 KB Output is correct
39 Execution timed out 1583 ms 70924 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 70924 KB Output is correct
2 Correct 3 ms 70924 KB Output is correct
3 Correct 2 ms 70924 KB Output is correct
4 Correct 2 ms 70924 KB Output is correct
5 Correct 2 ms 70924 KB Output is correct
6 Correct 2 ms 70924 KB Output is correct
7 Correct 2 ms 70924 KB Output is correct
8 Correct 2 ms 70924 KB Output is correct
9 Correct 2 ms 70924 KB Output is correct
10 Correct 3 ms 70924 KB Output is correct
11 Correct 3 ms 70924 KB Output is correct
12 Correct 3 ms 70924 KB Output is correct
13 Correct 2 ms 70924 KB Output is correct
14 Correct 3 ms 70924 KB Output is correct
15 Correct 2 ms 70924 KB Output is correct
16 Correct 2 ms 70924 KB Output is correct
17 Correct 3 ms 70924 KB Output is correct
18 Correct 3 ms 70924 KB Output is correct
19 Correct 3 ms 70924 KB Output is correct
20 Correct 3 ms 70924 KB Output is correct
21 Correct 2 ms 70924 KB Output is correct
22 Correct 2 ms 70924 KB Output is correct
23 Correct 5 ms 70924 KB Output is correct
24 Correct 5 ms 70924 KB Output is correct
25 Correct 4 ms 70924 KB Output is correct
26 Correct 4 ms 70924 KB Output is correct
27 Correct 5 ms 70924 KB Output is correct
28 Correct 5 ms 70924 KB Output is correct
29 Correct 6 ms 70924 KB Output is correct
30 Correct 5 ms 70924 KB Output is correct
31 Correct 5 ms 70924 KB Output is correct
32 Correct 5 ms 70924 KB Output is correct
33 Correct 142 ms 73668 KB Output is correct
34 Correct 226 ms 86164 KB Output is correct
35 Correct 174 ms 90060 KB Output is correct
36 Correct 266 ms 97720 KB Output is correct
37 Correct 106 ms 100736 KB Output is correct
38 Correct 51 ms 104772 KB Output is correct
39 Correct 83 ms 115492 KB Output is correct
40 Correct 79 ms 126360 KB Output is correct
41 Correct 417 ms 128516 KB Output is correct
42 Correct 51 ms 131488 KB Output is correct
43 Execution timed out 1564 ms 133556 KB Time limit exceeded
44 Halted 0 ms 0 KB -