Submission #640567

#	Time	Username	Problem	Language	Result	Execution time	Memory
640567		ymm	Gondola (IOI14_gondola)	C++17	55 / 100	35 ms	4816 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

int valid(int n, int inputSeq[])
{
	bool flg = 0;
	int off;
	set<int> s;
	Loop (i,0,n) {
		if (s.count(inputSeq[i]))
			return 0;
		s.insert(inputSeq[i]);
		if (inputSeq[i] <= n) {
			if (flg && (inputSeq[i]-1 - i + n) % n != off)
				return 0;
			if (!flg) {
				flg = 1;
				off = (inputSeq[i]-1 - i + n) % n;
			}
		}
	}
	return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int off = 0;
	Loop (i,0,n)
		if (gondolaSeq[i] <= n)
			off = (gondolaSeq[i]-1 - i + n) % n;
	vector<pii> a;
	Loop (i,0,n)
		a.push_back({gondolaSeq[i]-1, i});
	sort(a.begin(), a.end());
	int ans = 0;
	int nxt = n;
	Loop (i,0,n) {
		if (a[i].first < n)
			continue;
		int lst = (a[i].second + off) % n;
		while (nxt <= a[i].first) {
			replacementSeq[ans++] = lst+1;
			lst = nxt;
			nxt++;
		}
	}
	return ans;
}

//----------------------

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

• 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