oj.uz

Submission #1013636

# Submission time Handle Problem Language Result Execution time Memory
1013636 2024-07-03T18:00:12 Z Mardonbekhazratov Horses (IOI15_horses) C++17
54 / 100
 1500 ms 21700 KB 
#include "horses.h"
#include<algorithm>
#include<vector>
#include<iostream>
const long long INFLL=1e18;
const int INF=1e9;
const int MOD=1e9+7;

using namespace std;

int n;
vector<int>x,y;

int inv(int x){
	return x>1 ? MOD-(long long)(MOD/x)*inv(MOD%x)%MOD : x;
}

long long pref;

int get(){
	long long ans=1;
	long long pr=pref;
	for(int i=n-1;i>=0;i--){
		ans=max(ans,1LL*y[i]);
		if(ans>=INF){
			ans%=MOD;
			return pr*ans%MOD;
		}
		ans*=x[i];
		pr=pr*inv(x[i])%MOD;
	}
	return ans*pr%MOD;
}

int init(int N, int X[], int Y[]) {
	n=N;
	pref=1;
	x.resize(n);
	y.resize(n);
	for(int i=0;i<n;i++) x[i]=X[i],y[i]=Y[i],pref=pref*x[i]%MOD;
	return get();
}


int updateX(int pos, int val) {	
	pref=pref*inv(x[pos])%MOD*val%MOD;
	x[pos]=val;
	return get();
}

int updateY(int pos, int val) {
	y[pos]=val;
	return get();
}

Compilation message

horses.cpp: In function 'int inv(int)':
horses.cpp:14:13: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   14 | int inv(int x){
      |         ~~~~^
horses.cpp:12:12: note: shadowed declaration is here
   12 | vector<int>x,y;
      |            ^
horses.cpp:15:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 |  return x>1 ? MOD-(long long)(MOD/x)*inv(MOD%x)%MOD : x;
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:27:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   27 |    return pr*ans%MOD;
      |           ~~~~~~^~~~
horses.cpp:32:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   32 |  return ans*pr%MOD;
      |         ~~~~~~^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10628 KB Output is correct
2 Correct 63 ms 21656 KB Output is correct
3 Correct 60 ms 12816 KB Output is correct
4 Correct 63 ms 16868 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 2 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 4 ms 348 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 4 ms 348 KB Output is correct
32 Correct 2 ms 452 KB Output is correct
33 Correct 83 ms 8284 KB Output is correct
34 Correct 21 ms 8284 KB Output is correct
35 Correct 41 ms 8284 KB Output is correct
36 Correct 40 ms 8284 KB Output is correct
37 Correct 887 ms 8284 KB Output is correct
38 Correct 22 ms 11356 KB Output is correct
39 Execution timed out 1538 ms 10320 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 448 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 5 ms 348 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 5 ms 344 KB Output is correct
32 Correct 2 ms 452 KB Output is correct
33 Correct 40 ms 10580 KB Output is correct
34 Correct 61 ms 21700 KB Output is correct
35 Correct 53 ms 12884 KB Output is correct
36 Correct 57 ms 16896 KB Output is correct
37 Correct 90 ms 12112 KB Output is correct
38 Correct 22 ms 12112 KB Output is correct
39 Correct 44 ms 19032 KB Output is correct
40 Correct 44 ms 19028 KB Output is correct
41 Correct 875 ms 10256 KB Output is correct
42 Correct 20 ms 11604 KB Output is correct
43 Execution timed out 1562 ms 10332 KB Time limit exceeded
44 Halted 0 ms 0 KB -