Submission #1038410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038410		SonicML	Horses (IOI15_horses)	C++14	100 / 100	1350 ms	25768 KiB

horses

#include <iostream>
#include "horses.h"
#include <cmath>
     
using namespace std;
     
int const MODULO = 1e9+7;
     
int n, bucketSize, bucketNum;
     
int const NMAX = 5e5;
int x[1 + NMAX];
int y[1 + NMAX];
int preX[1 + NMAX];
int sufX[1 + NMAX];
     
int const BMAX = 750;
int bbest[1 + BMAX];
int prod[1 + BMAX];
    
bool compare(int a, int b) {
  if(b == -1 || a <= b) {
    return true;
  }
  return false;
}
     
int multiply(int a, int b) {
  if(a == -1 || b == -1 || (1LL * a * b >= MODULO )) {
    return -1;
  }
  return (a * b);
}
     
void buildBucket(int index) {
  int from = 1 + (index-1)*bucketSize, to = min(n, index*bucketSize);
  int pre = 1, suf = 1;
  prod[index] = 1;
  for(int i = from;i <= to;i++) {
    pre = multiply(pre, x[i]);
    prod[index] = (1LL * prod[index] * x[i]) % MODULO; 
    preX[i] = pre;
  }
  for(int i = to;i >= from;i--) {
    suf = multiply(suf, x[i]);
    sufX[i] = suf;
  }
  int best = from, multBest = y[from], multAux = 1;
  for(int i = from+1;i <= to;i++) {
    multAux = multiply(multAux, x[i]);
    if(compare(multBest, multiply(multAux, y[i]))) {
      best = i;
      multBest = y[best];
      multAux = 1;
    }
  }
  bbest[index] = best;
}
    
int computeSol() {
  int best = bbest[1], multBest = y[bbest[1]], multAux = 1;
  int prev = best;
  for(int index = 2;index <= bucketNum;index++) {
    int suf = 1, pre = 1;
    if(prev % bucketSize != 0) {
      suf = sufX[prev+1];
    }
    pre = preX[bbest[index]];  
    multAux = multiply(multAux, multiply(suf, pre));
    if(compare(multBest, multiply(multAux, y[bbest[index]]))) {
      best = bbest[index];
      multBest = y[best];
      multAux = 1;
    }
    prev = bbest[index]; 
  }
  int ans = 1, start = 1;
  for(int index = 1;index * bucketSize < best;index++) {
    ans = (1LL * ans * prod[index]) % MODULO;
    start = index * bucketSize + 1;
  }
  for(int i = start;i <= best;i++) {
    ans = (1LL * ans * x[i]) % MODULO;
  }
  ans = (1LL * ans * y[best]) % MODULO;
  return ans;
}
     
int init(int N, int X[], int Y[]) {
  n = N;
  bucketSize = sqrt(n);
  bucketNum = (n-1)/bucketSize+1;
  //cerr << n << ' ' << bucketSize << ' ' << bucketNum << '\n';
  for(int i = 1;i <= n;i++) {
    x[i] = X[i-1];
    y[i] = Y[i-1];
  }
  for(int i = 1;i <= bucketNum;i++) {
    buildBucket(i);
  }
  return computeSol();
}
     
int updateX(int pos, int val) {
  pos++;
  int bucketIndex = (pos-1)/bucketSize+1;
  x[pos] = val;
  //cerr << "X " << pos << ' ' << val << " : " << bucketIndex << "\n";
  buildBucket(bucketIndex);
  return computeSol();
}
     
int updateY(int pos, int val) {
  pos++;
  int bucketIndex = (pos-1)/bucketSize+1;
  y[pos] = val;
  //cerr << "Y " << pos << ' ' << val << " : " << bucketIndex << "\n";
  buildBucket(bucketIndex);
  return computeSol();
}

Compilation message (stderr)

horses.cpp: In function 'void buildBucket(int)':
horses.cpp:41:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   41 |     prod[index] = (1LL * prod[index] * x[i]) % MODULO;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp: In function 'int computeSol()':
horses.cpp:79:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |     ans = (1LL * ans * prod[index]) % MODULO;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp:83:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |     ans = (1LL * ans * x[i]) % MODULO;
      |           ~~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp:85:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   85 |   ans = (1LL * ans * y[best]) % MODULO;
      |         ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:91:20: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'int' may change value [-Wfloat-conversion]
   91 |   bucketSize = sqrt(n);
      |                ~~~~^~~

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