Submission #288494

#	Time	Username	Problem	Language	Result	Execution time	Memory
288494		AaronNaidu	Horses (IOI15_horses)	C++14	17 / 100	874 ms	13520 KiB

horses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

ll mod = 1000000007;
ll startOffWith = 1;
ld logStartOffWith = 0;
int n;
vector<ll> x, y;
vector<ld> prefSums;

int divide(ll num, ll denom) {
    ll inv = 1;
    ll expo = denom;
    for (int i = 0; i < 32; i++)
    {
        if ((mod-2) & (1<<i))
        {
            inv *= expo;
            inv %= mod;
        }
        expo *= expo;
        expo %= mod;
    }
    ll ans = num * inv;
    ans %= mod;
    return ans;
}

int solveProblem() {
    //cout << "Starting\n";
    int maxInd = -1;
    ld maxAns = -1;
    ld currAns = 0;
    for (int i = 0; i < n; i++)
    {
        currAns += log10(x[i]);
        currAns += log10(y[i]);
        if (currAns > maxAns)
        {
            maxAns = currAns;
            maxInd = i;
        }
        currAns -= log10(y[i]);
    }
    for (int i = 0; i < n-40; i++)
    {
        startOffWith *= x[i];
        startOffWith %= mod;
        logStartOffWith += log10(x[i]);
    }
    //cout << "half\n";
    ll finAns = 1;
    for (int i = 0; i < maxInd; i++)
    {
        finAns *= x[i];
        finAns %= mod;
    }
    finAns *= x[maxInd];
    finAns %= mod;
    finAns *= y[maxInd];
    finAns %= mod;
    return finAns;
}

int solveNewProblem() {
    int maxInd = -1;
    ld maxAns = -1;
    ld currAns = logStartOffWith;
    if (n-41 >= 0)
    {
        currAns += log10(y[n-41]);   
    }
    for (int i = max(n-40, 0); i < n; i++)
    {
        currAns += log10(x[i]);
        currAns += log10(y[i]);
        //prefSums[i] = currAns;
        if (currAns > maxAns)
        {
            maxAns = currAns;
            maxInd = i;
        }
        currAns -= log10(y[i]);
    }
    ll finAns = startOffWith;
    for (int i = max(n-40, 0); i < maxInd; i++)
    {
        finAns *= x[i];
        finAns %= mod;
    }
    finAns *= x[maxInd];
    finAns %= mod;
    finAns *= y[maxInd];
    finAns %= mod;
    return finAns;
}

int init(int N, int X[], int Y[]) {
    n = N;
    for (int i = 0; i < n; i++)
    {
        x.push_back(X[i]);
        y.push_back(Y[i]);
    }
    return solveProblem();    
}

int updateX(int pos, int val) {
    if (pos < n-40)
    {
        logStartOffWith -= log10(x[pos]);
        logStartOffWith += log10(val);
        startOffWith *= val;
        startOffWith = divide(startOffWith, x[pos]);
    }
    x[pos] = val;
    return solveNewProblem();
}

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

Compilation message (stderr)

horses.cpp: In function 'int divide(ll, ll)':
horses.cpp:28:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   28 |     return ans;
      |            ^~~
horses.cpp: In function 'int solveProblem()':
horses.cpp:64:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   64 |     return finAns;
      |            ^~~~~~
horses.cpp: In function 'int solveNewProblem()':
horses.cpp:97:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   97 |     return finAns;
      |            ^~~~~~

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