제출 #288526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288526		AaronNaidu	말 (IOI15_horses)	C++14	17 / 100	1359 ms	13908 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;
int subtract = 70;
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-subtract; i++)
    {
        startOffWith *= x[i];
        startOffWith %= mod;
        logStartOffWith += log10(x[i]);
    }
    //cout << "half\n";
    //cout << "Start off with " << startOffWith << " or log " << logStartOffWith << "\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-subtract-1 >= 0)
    {
        currAns += log10(y[n-subtract-1]);   
    }

    for (int i = max(n-subtract, 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]);
    }
    if (maxInd == -1)
    {
        int ans = startOffWith * y[n-subtract-1];
        ans %= mod;
        return ans;
    }
    
    ll finAns = startOffWith;
    for (int i = max(n-subtract, 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-subtract)
    {
        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();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int divide(ll, ll)':
horses.cpp:29:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   29 |     return ans;
      |            ^~~
horses.cpp: In function 'int solveProblem()':
horses.cpp:66:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   66 |     return finAns;
      |            ^~~~~~
horses.cpp: In function 'int solveNewProblem()':
horses.cpp:92:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   92 |         int ans = startOffWith * y[n-subtract-1];
horses.cpp:93:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   93 |         ans %= mod;
      |         ~~~~^~~~~~
horses.cpp:107:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  107 |     return finAns;
      |            ^~~~~~

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