Submission #1001650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001650		Ausp3x	Horses (IOI15_horses)	C++17	34 / 100	1592 ms	12944 KiB

horses

// 人外有人，天外有天
// author: Ausp3x

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "horses.h"
typedef long long             lng;
typedef unsigned int          uint;
typedef unsigned long long    ulng;
using namespace std;
using namespace __gnu_pbds;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

int const MOD = 1000000007;

int N;
vector<int> X, Y;

lng modPow(lng x, lng y) {
    lng res = 1;

    while (y > 0) {
        if (y & 1) {
            res *= x;
            res %= MOD;
        }

        y >>= 1;
        x *= x;
        x %= MOD;
    }

    return (res + MOD) % MOD;
}

lng allHorses = 1;
int getMaxValue(int opt) {
    if (opt == 1) {
        lng horses = 1;
        for (int i = 0; i < N; i++) {
            (horses *= X[i]) %= MOD;
            
            bool chk = true;
            lng cur = 1; 
            for (int j = i + 1; j < N; j++) {
                if (cur == INF32 || cur * X[j] > INF32) {
                    chk = false;
                    break;
                }
                cur *= X[j];

                if (cur * Y[j] > Y[i]) {
                    chk = false;
                    break;
                }
            }
                
            if (chk) {
                return horses * Y[i] % MOD;
            }
        }
    } else if (opt == 2) {
        lng horses = 1;
        for (int i = 0; i < 32; i++) {
            (horses *= X[i]) %= MOD;
            
            bool chk = true;
            lng cur = 1; 
            for (int j = i + 1; j < N; j++) {
                if (cur == INF32 || cur * X[j] > INF32) {
                    chk = false;
                    break;
                }
                cur *= X[j];

                if (cur * Y[j] > Y[i]) {
                    chk = false;
                    break;
                }
            }
                
            if (chk) {
                return horses * Y[i] % MOD;
            }
        }
        
        return allHorses * Y[N - 1] % MOD;
    }

    return -1;
}

bool allXG2 = true;
int init(int n, int x[], int y[]) {
    N = n;
    X.resize(n);
    Y.resize(n);
    for (int i = 0; i < n; i++) {
        if (x[i] < 2)
            allXG2 = false;

        (allHorses *= x[i]) %= MOD;
        X[i] = x[i];
        Y[i] = y[i];
    }

	return (allXG2 ? getMaxValue(2) : getMaxValue(1));
}

bool allValG2 = true;
int updateX(int pos, int val) {
    if (val < 2)
        allValG2 = false;

    (allHorses *= pow(X[pos], MOD - 2)) %= MOD;
    X[pos] = val;
    (allHorses *= X[pos]) %= MOD;

	return (allXG2 && allValG2 ? getMaxValue(2) : getMaxValue(1));
}

int updateY(int pos, int val) {
    if (val < 2)
        allValG2 = false;
    
    Y[pos] = val;

	return (allXG2 && allValG2 ? getMaxValue(2) : getMaxValue(1));
}

// int main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);

//     int x[3] = {2, 1, 3};
//     int y[3] = {3, 4, 1};
//     cout << init(3, x, y) << endl;
//     cout << updateY(1, 2) << endl;

//     return 0;
// }

Compilation message (stderr)

horses.cpp: In function 'int getMaxValue(int)':
horses.cpp:61:38: warning: conversion from 'lng' {aka 'long long int'} to 'int' may change value [-Wconversion]
   61 |                 return horses * Y[i] % MOD;
      |                        ~~~~~~~~~~~~~~^~~~~
horses.cpp:85:38: warning: conversion from 'lng' {aka 'long long int'} to 'int' may change value [-Wconversion]
   85 |                 return horses * Y[i] % MOD;
      |                        ~~~~~~~~~~~~~~^~~~~
horses.cpp:89:37: warning: conversion from 'lng' {aka 'long long int'} to 'int' may change value [-Wconversion]
   89 |         return allHorses * Y[N - 1] % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:117:38: warning: conversion from 'lng' {aka 'long long int'} to '__gnu_cxx::__promote_2<int, int, double, double>::__type' {aka 'double'} may change value [-Wconversion]
  117 |     (allHorses *= pow(X[pos], MOD - 2)) %= MOD;
      |                                      ^
horses.cpp:117:38: warning: conversion from '__gnu_cxx::__promote_2<int, int, double, double>::__type' {aka 'double'} to 'lng' {aka 'long long int'} may change value [-Wfloat-conversion]

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