Submission #137966

#	Time	Username	Problem	Language	Result	Execution time	Memory
137966		arthurconmy	Horses (IOI15_horses)	C++14	17 / 100	92 ms	12508 KiB

horses

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

using ll=long long;

const int p = 1000000007;
const int pLL = 1000000007LL;
const int MAXN = 500001; // 1-index that shit
const ll MAXP = 1000000000;

int n;
int X[MAXN];
int Y[MAXN];
ll x_prod=1;

int gcd(int a, int b, int &x, int &y)
{
	if(a%b == 1) // uh ... plug a = p in the real thing I guess then
	{
		x = 1;
		y = -int(a/b);

		return 1;
	}

	int d = gcd(b,a%b,x,y); 
	int old_x = x;

	x = y;
	y = old_x - int(a/b)*y;

	return d;
}

int mod_inv(int x)
{
	if(x==1) return 1; // thonking

	int x1=-1; 
	int y1=-1;
	
	gcd(p,x,x1,y1); // EDITING THIS DAMN FUNCTION !!!

	while(y1<0) y1+=p;

	return y1;
}

pair<ll,ll> mexico(pair<ll,ll> a, pair<ll,ll> b)
{
	if(b.second > MAXP) return a;

	if(a.first*b.second >= a.second*b.first) return a;
	return b;
}

int init(int N, int x[], int y[])
{
	n=N;

	for(int i=0; i<n; i++)
	{
		X[i+1]=x[i];

		x_prod *= ll(x[i]);
		x_prod %= pLL;
	}

	for(int i=0; i<n; i++)
	{
		Y[i+1]=y[i];
	}	

	pair<ll,ll> GL = {ll(Y[n]),1}; // gain and loss

	ll cur_loss = 1;
	int i = n-1;

	while(i>0 && cur_loss <= MAXP)
	{
		cur_loss *= X[i+1];
		GL = mexico(GL, make_pair(ll(Y[i]),cur_loss));
		i--;
	}

	// return x_prod * GL.first * mod_inv(GL.second)

	ll ans = x_prod * GL.first;
	ans %= pLL;
	ans *= ll(mod_inv(int(GL.second)));
	ans %= pLL;

	return ans; 
}

int updateX(int pos, int val)
{
	pos++;

	x_prod *= ll(mod_inv(X[pos]));
	x_prod %= pLL;
	x_prod *= val;
	x_prod %= pLL;

	pair<ll,ll> GL = {ll(Y[n]),1}; // gain and loss

	ll cur_loss = 1;
	int i = n-1;

	while(i>0 && cur_loss <= MAXP)
	{
		cur_loss *= X[i+1];
		GL = mexico(GL, make_pair(ll(Y[i]),cur_loss));
		i--;
	}

	// return x_prod * GL.first * mod_inv(GL.second)

	ll ans = x_prod * GL.first;
	ans %= pLL;
	ans *= ll(mod_inv(int(GL.second)));
	ans %= pLL;

	return ans; 
}

int updateY(int pos, int val)
{
	Y[++pos]=val;

	pair<ll,ll> GL = {ll(Y[n]),1}; // gain and loss

	ll cur_loss = 1;
	int i = n-1;

	while(i>0 && cur_loss <= MAXP)
	{
		cur_loss *= X[i+1];
		GL = mexico(GL, make_pair(ll(Y[i]),cur_loss));
		i--;
	}

	// return x_prod * GL.first * mod_inv(GL.second)

	ll ans = x_prod * GL.first;
	ans %= pLL;
	ans *= ll(mod_inv(int(GL.second)));
	ans %= pLL;

	return ans; 
}

#ifdef ARTHUR_LOCAL

	int X_raw[MAXN-1];
	int Y_raw[MAXN-1];

	int main()
	{
		X_raw[0]=2;
		X_raw[1]=1;
		X_raw[2]=3;
		Y_raw[0]=3;
		Y_raw[1]=4;
		Y_raw[2]=1;

		cout << init(3,X_raw,Y_raw) << endl;
		cout << updateY(1,2) << endl;
	}
#endif

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:93:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return ans; 
         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:124:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return ans; 
         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:150:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return ans; 
         ^~~

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