| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1272739 | burnthememory | Xylophone (JOI18_xylophone) | C++20 | 0 ms | 0 KiB |
#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll N = 10*1e5;
//
//ll query(ll l, ll r){
// cout << l << " " << r << endl;
// ll ret; cin >> ret;
// return ret;
//}
void solve(ll n) {
vector<vector<ll>> seg(n+5, vector<ll>(n+5, 0));
for(int i = 1; i <= n; i++){
if(i+1 <= n) seg[i][i+1] = query(i, i+1);
if(i+2 <= n) seg[i][i+2] = query(i, i+2);
}
vector<ll> mn(3, 0), x(3, 1), koef(3, 1), kiri(3, 0);
vector<vector<ll>> type(3, vector<ll> (n+10, 0));
type[1][1] = 0; type[1][2] = seg[1][2];
type[2][1] = 0; type[2][2] = (seg[1][2] * -1);
for(int i = 1; i+2 <= n; i++){
koef[1] = koef[2] = 1;
ll lef = seg[i][i+1], rig = seg[i+1][i+2], all = seg[i][i+2];
if(lef+rig == all){
if(type[1][i+1] < 0) koef[1] = -1;
else koef[1] = 1;
}else{
if(type[1][i+1] < 0) koef[1] = 1;
else koef[1] = -1;
}
koef[2] = koef[1]*-1;
//
for(int j = 1; j <= 2; j++){
type[j][i+2] = (rig*koef[j]);
}
}
// swap(x[1], x[2]);
vector<vector<ll>> arr(3); arr[1].pb(x[1]); arr[2].pb(x[2]);
for(int i = 2; i <= n; i++){
for(int j = 1; j <= 2; j++){
type[j][i] = (type[j][i]+type[j][i-1]);
}
}
// ll idx = 2;
// if(kiri[1] < kiri[2]) idx = 1;
//
for(int i = 1; i <= n; i ++){
x[1] = min(x[1], type[1][i]);
x[2] = min(x[2], type[2][i]);
}
x[1]=1-x[1];
x[2]=1-x[2];
for(int i = 1; i <= n; i ++){
type[1][i] += x[1];
type[2][i] += x[2];
if(type[1][i] == 1) kiri[1] = i;
if(type[2][i] == 1) kiri[2] = i;
}
ll idx = 2;
if(kiri[1] < kiri[2]) idx = 1;
for(int i = 1; i <= n; i++){
answer(i, type[idx][i]);
}
}
//int main(){
//// ios::sync_with_stdio(false);
//// cin.tie(nullptr);
// ll t=1;
// cin >> t;
//// while(t--)
// solve(t);
//}
//