제출 #1281511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281511		Jawad_Akbar_JJ	곤돌라 (IOI14_gondola)	C++17	55 / 100	36 ms	6052 KiB

gondola

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include "gondola.h"

using namespace std;

int valid(int n, int seq[]){
	map<int,int> mp;
	for (int i=0;i<n;i++){
		if (mp.find(seq[i]) != mp.end())
			return 0;
		mp[seq[i]];
	}

	vector<int> vc(n + 1);
	for (int i=0;i<=n;i++){
		if (i == n)
			return 1;
		if (seq[i] <= n){
			for (int j=i;j<i + n;j++)
				vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
			break;
		}
	}

	for (int i=1;i<=n;i++)
		if (vc[i] <= n and vc[i] != i)
			return 0;
	return 1;
}

int replacement(int n, int seq[], int ans[]){
	vector<int> vc(n + 1);
	vector<pair<int,int>> vc2;

	for (int i=0;i<=n;i++){
		if (i == n){
			for (int j=0;j<n;j++)
				vc[j+1] = seq[j];
		}
		else if (seq[i] <= n){
			for (int j=i;j<i + n;j++)
				vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
			break;
		}
	}

	for (int i=1;i<=n;i++){
		if (vc[i] > n)
			vc2.push_back({vc[i], i});
	}
	sort(begin(vc2), end(vc2));

	int cur = n + 1, sz = 0;
	for (auto [vl, id] : vc2){
		// cout<<cur<<" "<<vl<<" "<<id<<endl;
		while (cur < vl)
			ans[sz++] = id, id = cur++;
		ans[sz++] = id;
		cur++;
	}
	return sz;
}

int countReplacement(int n, int seq[]){
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10