Submission #1286507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286507		tschav_	말 (IOI15_horses)	C++20	0 / 100	7 ms	4160 KiB

horses

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> x, y;
int n;
int m;
ll prod = 1;
int idx = -1;
vector<int> st;
static const ll MOD = 1e9+7;

ll binpow(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll solve() {
	ll mx = (idx == -1 ? 0 : y[st[idx]]);
	ll curr = 1;
	for(int i = idx+1; i < m; ++i){
		curr *= x[st[i]];
		if(curr * y[st[i]] > mx) {
			mx = curr * y[st[i]];
		}
	}
	return (mx%MOD * prod%MOD) % MOD;
}

void ind() {
	idx = -1;
	ll P = 1ll;
	for(int i = m-1; i >= 0; --i) {
		if(P * x[st[i]] > 1e9) {
			idx=i;
			break;
		} else P *= x[st[i]];
	}
}

void getprod() {
	prod = 1ll;
	for(int i = 0; i <= idx; ++i){
		prod = (prod * x[st[i]]) % MOD;
	}
}

int init(int N, int X[], int Y[]) {
	n = N;
	x.resize(sizeof(X),0ll);
	y.resize(sizeof(Y),0ll);
	for(int i = 0; i < n; ++i) {
		x[i] = X[i];
		y[i] = Y[i];
		st.push_back(i);
	}
	m = st.size();

	ind();
	getprod();
	return int(solve());
}

int updateX(int pos, int val) {
	ll old = x[pos];
	x[pos] = val;
	ind();
	if(pos <= idx) {
        prod = (prod * binpow(old, MOD-2,MOD)) % MOD;
        prod = (prod * val) % MOD;
	}
	return int(solve());
}

int updateY(int pos, int val) {
	y[pos] = val;
	ind();
	return int(solve());
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:56:25: warning: 'sizeof' on array function parameter 'X' will return size of 'int*' [-Wsizeof-array-argument]
   56 |         x.resize(sizeof(X),0ll);
      |                        ~^~
horses.cpp:54:21: note: declared here
   54 | int init(int N, int X[], int Y[]) {
      |                 ~~~~^~~
horses.cpp:57:25: warning: 'sizeof' on array function parameter 'Y' will return size of 'int*' [-Wsizeof-array-argument]
   57 |         y.resize(sizeof(Y),0ll);
      |                        ~^~
horses.cpp:54:30: note: declared here
   54 | int init(int N, int X[], int Y[]) {
      |                          ~~~~^~~

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