제출 #1004915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1004915		pawned	말 (IOI15_horses)	C++17	54 / 100	1562 ms	25524 KiB

horses

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "horses.h"

const ll MOD = 1e9 + 7;
const ll MAX = 1e9 + 5;

ll norm(ll x) {
	x %= MOD;
	x += MOD;
	x %= MOD;
	return x;
}

ll binpow(ll x, ll y) {
	x = norm(x);
	ll res = 1;
	while (y > 0) {
		if (y % 2 == 1)
			res = norm(res * x);
		x = norm(x * x);
		y /= 2;
	}
	return res;
}

ll inv(ll x) {
	return binpow(x, MOD - 2);
}

int N;

vi X;
vi Y;

ll prodall = 1;	// product of all X_i

ll solve() {
	int bestp = N - 1;
	ll currn = Y[N - 1];
	ll currd = 1;
	ll bestn = currn;
	ll bestd = currd;
	for (int i = N - 2; i >= 0; i--) {
		currn = Y[i];
		currd *= X[i + 1];
		if (currd >= MAX)
			break;
		if (currn * bestd > bestn * currd) {
			bestp = i;
			bestn = currn;
			bestd = currd;
		}
	}
	ll ans = prodall;
	for (int i = bestp + 1; i < N; i++) {
		ans *= inv(X[i]);
		ans = norm(ans);
	}
	ans *= Y[bestp];
	ans = norm(ans);
	return ans;
}

int init(int n, int x[], int y[]) {
	N = n;
	X = vi(N); Y = vi(N);
	for (int i = 0; i < N; i++) {
		X[i] = x[i];
		Y[i] = y[i];
	}
	for (int i = 0; i < N; i++) {
		prodall *= X[i];
		prodall = norm(prodall);
	}
	ll ans = solve();
	return (int)(ans);
}

int updateX(int pos, int val) {
	prodall = norm(prodall * inv(X[pos]));
	X[pos] = val;
	prodall = norm(prodall * X[pos]);
	ll ans = solve();
	return (int)(ans);
}

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

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23