oj.uz

Submission #1001746

# Submission time Handle Problem Language Result Execution time Memory
1001746 2024-06-19T07:27:38 Z Ausp3x Horses (IOI15_horses) C++17
0 / 100
 43 ms 13020 KB 
// 人外有人，天外有天
// 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 = N - 64; 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;
            }
        }
    }
 
    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

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: In function 'int updateX(int, int)':
horses.cpp:115: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]
  115 |     (allHorses *= pow(X[pos], MOD - 2)) %= MOD;
      |                                      ^
horses.cpp:115: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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 13020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -