Submission #937555

#	Time	Username	Problem	Language	Result	Execution time	Memory
937555		Litusiano	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	101 ms	35780 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin>>n;
	vector<int> v(n); for(int& i : v) cin>>i;
	unordered_map<int,int> cmp;
	unordered_map<int,int> rev;
	int cur = 1;
	for(int i = 0; i<n; i++){
		if(cmp.find(v[i]) == cmp.end()){
			rev[cur] = v[i];
			cmp[v[i]] = cur; cur++;
		}
		v[i] = cmp[v[i]];
	}
	vector<vector<int>> colors(cur);
	// map<int,int> rev;
	for(int i = n-1; i>=0; i--){
		if(v[i] == v[0]){
			for(int j = 0; j<i; j++){
				v[j] = v[i];
			}
			break;
		}
	}
	for(int i = 0; i<n; i++){
		// rev[i] = v[i];
		if(colors[v[i]].size() > 0){
			int idx = colors[v[i]][colors[v[i]].size()-1];
			for(int j = idx+1; j<=i; j++){
				if(v[j] == v[i]) break;
				colors[v[j]].pop_back();
				v[j] = v[i];
				colors[v[i]].push_back(j);
			}
			colors[v[i]].push_back(i);
		}
		else{
			// rev[i] = v[i];
			colors[v[i]].push_back(i);
		}
	}
	for(int i = 0; i<n; i++){
		cout<<rev[v[i]]<<" ";
	}
	cout<<endl;
}

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