oj.uz

Submission #1038410

# Submission time Handle Problem Language Result Execution time Memory
1038410 2024-07-29T19:00:35 Z SonicML Horses (IOI15_horses) C++14
100 / 100
 1350 ms 25768 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6592 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6592 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6596 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 2 ms 6492 KB Output is correct
24 Correct 2 ms 6744 KB Output is correct
25 Correct 2 ms 6492 KB Output is correct
26 Correct 1 ms 6632 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6612 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 13500 KB Output is correct
2 Correct 999 ms 25596 KB Output is correct
3 Correct 1050 ms 16932 KB Output is correct
4 Correct 1350 ms 20608 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 2 ms 6492 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 146 ms 16136 KB Output is correct
34 Correct 134 ms 16136 KB Output is correct
35 Correct 108 ms 22988 KB Output is correct
36 Correct 135 ms 23052 KB Output is correct
37 Correct 120 ms 14172 KB Output is correct
38 Correct 122 ms 15204 KB Output is correct
39 Correct 118 ms 14172 KB Output is correct
40 Correct 130 ms 18084 KB Output is correct
41 Correct 98 ms 14232 KB Output is correct
42 Correct 75 ms 14352 KB Output is correct
43 Correct 36 ms 18512 KB Output is correct
44 Correct 36 ms 18512 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6596 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6588 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6592 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6488 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 2 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 2 ms 6492 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 687 ms 16848 KB Output is correct
34 Correct 1040 ms 25768 KB Output is correct
35 Correct 1045 ms 16728 KB Output is correct
36 Correct 1263 ms 21092 KB Output is correct
37 Correct 144 ms 16208 KB Output is correct
38 Correct 135 ms 16104 KB Output is correct
39 Correct 105 ms 22948 KB Output is correct
40 Correct 142 ms 22884 KB Output is correct
41 Correct 138 ms 14316 KB Output is correct
42 Correct 117 ms 15280 KB Output is correct
43 Correct 135 ms 14172 KB Output is correct
44 Correct 134 ms 18076 KB Output is correct
45 Correct 103 ms 14248 KB Output is correct
46 Correct 77 ms 14168 KB Output is correct
47 Correct 36 ms 18488 KB Output is correct
48 Correct 36 ms 18436 KB Output is correct
49 Correct 1092 ms 17988 KB Output is correct
50 Correct 1113 ms 18188 KB Output is correct
51 Correct 636 ms 24852 KB Output is correct
52 Correct 1004 ms 24328 KB Output is correct
53 Correct 1063 ms 16536 KB Output is correct
54 Correct 1022 ms 17040 KB Output is correct
55 Correct 1091 ms 15128 KB Output is correct
56 Correct 1012 ms 19792 KB Output is correct
57 Correct 839 ms 15956 KB Output is correct
58 Correct 651 ms 16292 KB Output is correct
59 Correct 36 ms 18524 KB Output is correct