답안 #60116 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60116	2018-07-23T16:53:46 Z	dukati8	말 (IOI15_horses)	C++14	54 / 100	1500 ms	104996 KB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i<int(b); i++)
using namespace std;
int n;
long long x[500000],y[500000];
long long m=1000000000+7;
long long product;

pair<long long,long long> invgcd(long long a, long long b) {
	//Returns x and y such that ax+by=1
	if (a==1 && b==0) return make_pair(1,0);
	long long c=a%b;
	long long d=a/b;
	pair<long long, long long > ans = invgcd(b,c);
	return make_pair(ans.second,ans.first-ans.second*d);
}
long long inverse2(long long a) {
	pair<long long, long long > ans = invgcd(m,a);
	return ans.second+m;
}
long long powsmart(long long a,long long b) {
	if (b==1) return a;
  long long x=powsmart(a,b/2);
  x=(x*x)%m;
	if (b%2==0) {
		return x;
	}
	else
		return (a*x)%m;
}
long long inverse( long long a) {
	//calculate a**(m-2)
	return powsmart(a%m,m-2);

}
int init(int N, int X[], int Y[]) {
	n=N;
	rep (i,0,n) {
		x[i]=X[i];
		y[i]=Y[i];
	}
	product=1;
	rep (i,0,n) {
		product*=x[i];
		product%=m;
	}
	long long hi=y[n-1];
	long long divide=1;
	for (int i = n-2; i>=0; i--) {
		hi*=x[i+1];
		hi=max(hi,y[i]);
		divide*=x[i+1];
		if (hi>=1000000000) break;
	}
	long long ans=(hi%m)*product;
	ans%=m;
	ans*=inverse(divide);
	ans%=m;
	return ans;


}

int updateX(int pos, int val) {
	product*=inverse(x[pos]);
	product%=m;
	product*=val;
	product%=m;
	x[pos]=val;

	long long hi=y[n-1];
	long long divide=1;
	for (int i = n-2; i>=0; i--) {
		hi*=x[i+1];
		hi=max(hi,y[i]);
		divide*=x[i+1];
		if (hi>=1000000000) break;
	}
	long long ans=(hi%m)*product;
	ans%=m;
	ans*=inverse(divide);
	ans%=m;
	return ans;
}

int updateY(int pos, int val) {
	y[pos]=val;
	long long hi=y[n-1];
	long long divide=1;
	for (int i = n-2; i>=0; i--) {
		hi*=x[i+1];
		hi=max(hi,y[i]);
		divide*=x[i+1];
		if (hi>=1000000000) break;
	}
	long long ans=(hi%m)*product;
	ans%=m;
	ans*=inverse(divide);
	ans%=m;
	return ans;
}

Compilation message

horses.cpp: In function 'long long int powsmart(long long int, long long int)':
horses.cpp:25:13: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   long long x=powsmart(a,b/2);
             ^
horses.cpp:7:11: note: shadowed declaration is here
 long long x[500000],y[500000];
           ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:61:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:85:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:102:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	488 KB	Output is correct
5	Correct	3 ms	596 KB	Output is correct
6	Correct	3 ms	596 KB	Output is correct
7	Correct	2 ms	596 KB	Output is correct
8	Correct	3 ms	652 KB	Output is correct
9	Correct	3 ms	780 KB	Output is correct
10	Correct	3 ms	780 KB	Output is correct
11	Correct	3 ms	780 KB	Output is correct
12	Correct	3 ms	780 KB	Output is correct
13	Correct	2 ms	780 KB	Output is correct
14	Correct	2 ms	780 KB	Output is correct
15	Correct	3 ms	780 KB	Output is correct
16	Correct	2 ms	780 KB	Output is correct
17	Correct	3 ms	780 KB	Output is correct
18	Correct	3 ms	780 KB	Output is correct
19	Correct	3 ms	780 KB	Output is correct
20	Correct	3 ms	780 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	780 KB	Output is correct
2	Correct	2 ms	780 KB	Output is correct
3	Correct	2 ms	780 KB	Output is correct
4	Correct	2 ms	780 KB	Output is correct
5	Correct	3 ms	780 KB	Output is correct
6	Correct	2 ms	780 KB	Output is correct
7	Correct	2 ms	780 KB	Output is correct
8	Correct	3 ms	780 KB	Output is correct
9	Correct	3 ms	780 KB	Output is correct
10	Correct	2 ms	780 KB	Output is correct
11	Correct	3 ms	780 KB	Output is correct
12	Correct	3 ms	780 KB	Output is correct
13	Correct	3 ms	780 KB	Output is correct
14	Correct	3 ms	780 KB	Output is correct
15	Correct	2 ms	780 KB	Output is correct
16	Correct	2 ms	780 KB	Output is correct
17	Correct	2 ms	780 KB	Output is correct
18	Correct	3 ms	780 KB	Output is correct
19	Correct	3 ms	780 KB	Output is correct
20	Correct	0 ms	780 KB	Output is correct
21	Correct	3 ms	780 KB	Output is correct
22	Correct	2 ms	780 KB	Output is correct
23	Correct	6 ms	780 KB	Output is correct
24	Correct	4 ms	780 KB	Output is correct
25	Correct	5 ms	780 KB	Output is correct
26	Correct	5 ms	780 KB	Output is correct
27	Correct	6 ms	780 KB	Output is correct
28	Correct	6 ms	780 KB	Output is correct
29	Correct	8 ms	780 KB	Output is correct
30	Correct	7 ms	780 KB	Output is correct
31	Correct	7 ms	780 KB	Output is correct
32	Correct	5 ms	780 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	178 ms	13372 KB	Output is correct
2	Correct	260 ms	13372 KB	Output is correct
3	Correct	264 ms	17212 KB	Output is correct
4	Correct	316 ms	24892 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	24892 KB	Output is correct
2	Correct	3 ms	24892 KB	Output is correct
3	Correct	3 ms	24892 KB	Output is correct
4	Correct	3 ms	24892 KB	Output is correct
5	Correct	2 ms	24892 KB	Output is correct
6	Correct	3 ms	24892 KB	Output is correct
7	Correct	3 ms	24892 KB	Output is correct
8	Correct	3 ms	24892 KB	Output is correct
9	Correct	3 ms	24892 KB	Output is correct
10	Correct	3 ms	24892 KB	Output is correct
11	Correct	3 ms	24892 KB	Output is correct
12	Correct	3 ms	24892 KB	Output is correct
13	Correct	2 ms	24892 KB	Output is correct
14	Correct	4 ms	24892 KB	Output is correct
15	Correct	3 ms	24892 KB	Output is correct
16	Correct	3 ms	24892 KB	Output is correct
17	Correct	3 ms	24892 KB	Output is correct
18	Correct	3 ms	24892 KB	Output is correct
19	Correct	2 ms	24892 KB	Output is correct
20	Correct	3 ms	24892 KB	Output is correct
21	Correct	2 ms	24892 KB	Output is correct
22	Correct	3 ms	24892 KB	Output is correct
23	Correct	5 ms	24892 KB	Output is correct
24	Correct	5 ms	24892 KB	Output is correct
25	Correct	4 ms	24892 KB	Output is correct
26	Correct	5 ms	24892 KB	Output is correct
27	Correct	5 ms	24892 KB	Output is correct
28	Correct	5 ms	24892 KB	Output is correct
29	Correct	9 ms	24892 KB	Output is correct
30	Correct	6 ms	24892 KB	Output is correct
31	Correct	8 ms	24892 KB	Output is correct
32	Correct	5 ms	24892 KB	Output is correct
33	Correct	107 ms	24892 KB	Output is correct
34	Correct	63 ms	27828 KB	Output is correct
35	Correct	103 ms	38792 KB	Output is correct
36	Correct	96 ms	49620 KB	Output is correct
37	Correct	562 ms	51792 KB	Output is correct
38	Correct	65 ms	54732 KB	Output is correct
39	Execution timed out	1563 ms	56608 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	56608 KB	Output is correct
2	Correct	2 ms	56608 KB	Output is correct
3	Correct	2 ms	56608 KB	Output is correct
4	Correct	3 ms	56608 KB	Output is correct
5	Correct	4 ms	56608 KB	Output is correct
6	Correct	3 ms	56608 KB	Output is correct
7	Correct	3 ms	56608 KB	Output is correct
8	Correct	2 ms	56608 KB	Output is correct
9	Correct	4 ms	56608 KB	Output is correct
10	Correct	3 ms	56608 KB	Output is correct
11	Correct	2 ms	56608 KB	Output is correct
12	Correct	3 ms	56608 KB	Output is correct
13	Correct	3 ms	56608 KB	Output is correct
14	Correct	4 ms	56608 KB	Output is correct
15	Correct	3 ms	56608 KB	Output is correct
16	Correct	1 ms	56608 KB	Output is correct
17	Correct	3 ms	56608 KB	Output is correct
18	Correct	3 ms	56608 KB	Output is correct
19	Correct	4 ms	56608 KB	Output is correct
20	Correct	3 ms	56608 KB	Output is correct
21	Correct	3 ms	56608 KB	Output is correct
22	Correct	3 ms	56608 KB	Output is correct
23	Correct	5 ms	56608 KB	Output is correct
24	Correct	6 ms	56608 KB	Output is correct
25	Correct	5 ms	56608 KB	Output is correct
26	Correct	5 ms	56608 KB	Output is correct
27	Correct	5 ms	56608 KB	Output is correct
28	Correct	5 ms	56608 KB	Output is correct
29	Correct	8 ms	56608 KB	Output is correct
30	Correct	7 ms	56608 KB	Output is correct
31	Correct	8 ms	56608 KB	Output is correct
32	Correct	5 ms	56608 KB	Output is correct
33	Correct	190 ms	57732 KB	Output is correct
34	Correct	262 ms	57732 KB	Output is correct
35	Correct	246 ms	61600 KB	Output is correct
36	Correct	324 ms	69252 KB	Output is correct
37	Correct	105 ms	72188 KB	Output is correct
38	Correct	73 ms	76056 KB	Output is correct
39	Correct	98 ms	86996 KB	Output is correct
40	Correct	99 ms	97784 KB	Output is correct
41	Correct	543 ms	100288 KB	Output is correct
42	Correct	66 ms	103012 KB	Output is correct
43	Execution timed out	1561 ms	104996 KB	Time limit exceeded
44	Halted	0 ms	0 KB	-

답안 #60116

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 23.0

Subtask #5 0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 23.0

Subtask #5
0 / 23.0