답안 #60116

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