Submission #640570

#	Time	Username	Problem	Language	Result	Execution time	Memory
640570		ymm	Gondola (IOI14_gondola)	C++17	100 / 100	53 ms	6024 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;
}

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

const int mod = 1e9 + 9;

ll mpow(ll x, ll y) {ll ans=1;while(y){ans=y&1?ans*x%mod:ans;x=x*x%mod;y>>=1;}return ans;}

int countReplacement(int n, int inputSeq[])
{
	if (!valid(n, inputSeq))
		return 0;
	int off = 0;
	Loop (i,0,n)
		if (inputSeq[i] <= n)
			off = (inputSeq[i]-1 - i + n) % n;
	vector<pii> a;
	Loop (i,0,n)
		a.push_back({inputSeq[i]-1, i});
	sort(a.begin(), a.end());
	ll ans = 1;
	int nxt = n;
	int cnt = n;
	Loop (i,0,n) {
		--cnt;
		if (a[i].first < n)
			continue;
		ans = ans * mpow(cnt + 1, a[i].first - nxt) % mod;
		nxt = a[i].first + 1;
	}
	if (a[0].first >= n)
		ans = ans*n % mod;
	return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:68:6: warning: variable 'off' set but not used [-Wunused-but-set-variable]
   68 |  int off = 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: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10