제출 #1271532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271532		WH8	Xylophone (JOI18_xylophone)	C++20	100 / 100	26 ms	624 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

void solve(int n) {
	vector<int> d(n+1, 0);
	vector<vector<int>> pos(2, vector<int>(n+1, 0));
	for(int i=2;i<=n;i++){
		d[i]=query(i-1, i);
	}
	if(n==2){
		answer(1, 1);
		answer(2, 2);
		return;
	}
	pos[0][2]=d[2], pos[1][2]=-d[2];
	
	for(int i=3;i<=n;i++){
		int c=query(i-2, i);
		if(c==d[i]+d[i-1]){ // same direction
			pos[0][i]=(pos[0][i-1]<0?-d[i]:d[i]);
			pos[1][i]=(pos[1][i-1]<0?-d[i]:d[i]);
		}
		else {
			pos[0][i]=(pos[0][i-1]<0?d[i]:-d[i]);
			pos[1][i]=(pos[1][i-1]<0?d[i]:-d[i]);
		}
	}
	//~ for(int i=2;i<=n;i++){
		//~ cout<<pos[0][i]<<" " << pos[1][i]<<endl;
	//~ }
	int correct=-1;
	vector<vector<int>> sm(2, vector<int>(n+1, 0));
	vector<pair<int,int>> mn={{1, 1}, {1,1}};
	sm[0][1]=sm[1][1]=1;
	for(int i=2;i<=n;i++){
		sm[0][i]=sm[0][i-1]+pos[0][i];
		mn[0]=min(mn[0], {sm[0][i], i});
		sm[1][i]=sm[1][i-1]+pos[1][i];
		mn[1]=min(mn[1], {sm[1][i], i});
		//~ cout<<sm[0][i]<<" "<<sm[1][i]<<endl;
	}
	vector<vector<int>> res(2, vector<int>(n+1, 0));
	for(int i=1;i<=n;i++){
		res[0][i]=sm[0][i]+1-mn[0].first;
		res[1][i]=sm[1][i]+1-mn[1].first;
		//~ cout<<res[0][i]<<" "<<res[1][i]<<endl;
		if(res[0][i]==1 and correct==-1){
			correct=0;
		}
		if(res[1][i]==1 and correct==-1){
			correct=1;
		}
	}
	//~ for(int i=1;i<=n;i++)cout<<res[correct][i]<<endl;
	for(int i=1;i<=n;i++){
		answer(i, res[correct][i]);
	}	
}

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