Submission #784112

#	Time	Username	Problem	Language	Result	Execution time	Memory
784112		peijar	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	198 ms	15180 KiB

Main

#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
	// 入力
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
 
	// 各色に対して「最も右の位置」を前計算
	map<int, int> rightmost;
	for (int i = 0; i < N; i++) {
		rightmost[A[i]] = max(rightmost[A[i]], i);
	}
 
	// 塗っていく
	vector<int> answer(N);
	int curpos = 0;
	while (curpos != N) {
		int nextpos = rightmost[A[curpos]] + 1;
		for (int i = curpos; i < nextpos; i++) {
			answer[i] = A[curpos];
		}
		curpos = nextpos;
	}
 
	// 出力
	for (int i = 0; i < N; i++) {
		cout << answer[i] << '\n';
	}
 
	return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40