제출 #1272740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272740		burnthememory	Xylophone (JOI18_xylophone)	C++20	100 / 100	116 ms	196816 KiB

xylophone

#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(int 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);
//}

//

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53