답안 #743757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
743757	2023-05-18T00:11:48 Z	Abrar_Al_Samit	말 (IOI15_horses)	C++17	37 / 100	449 ms	29476 KB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;

const int nax = 5e5 + 2;
const int mod = 1e9 + 7;
const int MX = 1e9;
long long x[nax], y[nax];
long long preprod[nax];
int n;

long long mul(long long a, long long b) {
	return (a * b) % mod;
}
long long quickpow(long long a, long long b) {
	long long ret = 1;
	while(b) {
		if(b&1) ret = mul(ret, a);
		a = mul(a, a);
		b >>= 1;
	}
	return ret;
}
int get() {
	for(int i=max(0, n-30); i<n; ++i) {
		long long cur = preprod[i];

		long long cnt = 1;
		bool ok = false;
		for(int j=i+1; j<n; ++j) {
			cnt *= x[j];
			if(cnt * y[j] > y[i]) {
				ok = true;
				break;
			}
			if(cnt>MX) {
				ok = true;
				break;
			}
		}
		if(!ok) {
			return (cur * y[i]) % mod;
		}
	}
}
int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=0; i<n; ++i) {
		x[i] = X[i], y[i] = Y[i];
		preprod[i] = x[i];
		if(i) preprod[i] = mul(preprod[i], preprod[i-1]);
	}
	return get();
}

int updateX(int pos, int val) {	
	for(int i=max(pos, n-30); i<n; ++i) {
		preprod[i] = mul(preprod[i], quickpow(x[pos], mod-2));
		preprod[i] = mul(preprod[i], val);
	}
	x[pos] = val;
	return get();
}

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

Compilation message

horses.cpp: In function 'int get()':
horses.cpp:42:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |    return (cur * y[i]) % mod;
      |           ~~~~~~~~~~~~~^~~~~
horses.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

Subtask #1

17.0 / 17.0

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

Subtask #2

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Incorrect	3 ms	340 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	18520 KB	Output is correct
2	Correct	279 ms	29476 KB	Output is correct
3	Correct	243 ms	20808 KB	Output is correct
4	Correct	449 ms	24516 KB	Output is correct

Subtask #4

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Incorrect	3 ms	340 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Incorrect	2 ms	340 KB	Output isn't correct
24	Halted	0 ms	0 KB	-