Submission #52440

#	Time	Username	Problem	Language	Result	Execution time	Memory
52440		shoemakerjo	Gondola (IOI14_gondola)	C++14	40 / 100	65 ms	6032 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
const int mod = 1000000009;

int modpow(int base, int p) {
	if (p == 0) return 1;
	if (p & 1) {
		int tmp = modpow(base, p-1);
		return (tmp*1LL*base)%mod;
	}
	int tmp = modpow(base, p/2);
	return (tmp*1LL*tmp)%mod;
}

int valid(int n, int inputSeq[])
{
	int minval = n+1;
	int minind = 0;
	set<int> seen;
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] < minval) {
			minval = inputSeq[i];
			minind = i;
		}
		if (seen.count(inputSeq[i]) > 0) return 0;
		seen.insert(inputSeq[i]);
	}
	if (minval > n) return 1; //i think this is fine then

	int cur = minind;
	int ivals[n];
	int cv = minval;
	//cannot appear after something that is greater than me and still less than n
	int maxv = -1;
	for (int i = 0; i < n; i++) {
		ivals[cur] = cv;
		cur = (cur+1)%n;
		cv = (cv+1)%n;
		if (cv == 0) cv += n;
	}
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] <= n && inputSeq[i] != ivals[i]) {
			return 0;
		}
	}
	return 1; //nothing was bad enough to return 0
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{	
	//find a valid replacement sequence

	int sz = 0; //get what becomes what

	int lowbelow = -1;
	int lowind = -1;
	int maxval = -1;
	map<int, int> ch;
	int maxind = -1;
	int cvals[n];
	for (int i = 0; i < n; i++) {
		cvals[i] = gondolaSeq[i];
		if (gondolaSeq[i] <= n) {
			if (gondolaSeq[i] < lowbelow || lowbelow == -1) {
				lowbelow = gondolaSeq[i];
				lowind = i;
			}

		}
		else {
			ch[gondolaSeq[i]] = i;
		}
		if (gondolaSeq[i] > maxval) {
			maxval = gondolaSeq[i];
			maxind = i;
		}
	}
	//do not use a vector for ans just add stuff to replacementSeq as you go and increment sz
	int initialvals[n];
	if (lowind == -1) {
		//just do stuff idk - for now we will just do nothing
	}
	int cv = gondolaSeq[lowind];
	int ci = lowind;
	for (int i = 0; i < n; i++) {
		initialvals[ci] = cv;
		ci = (ci+1)%n;
		cv = (cv+1)%n;
		if (cv == 0) cv += n;
	}
	for (int i = n+1; i <= maxval; i++) {
		if (ch[i]) {
			replacementSeq[sz++] = ch[i];
		}
		else {
			replacementSeq[sz++] = cvals[maxind];
			cvals[maxind] = i;
		}
	}

	return sz;
}

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

int countReplacement(int n, int inputSeq[])
{
	if (valid(n, inputSeq) == 0) { //just add this in there
		return 0;
	}
	int ans = 1;
	vector<int> aftn;
	aftn.push_back(n);
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] > n) {
			aftn.push_back(inputSeq[i]);
		}
	}
	sort(aftn.begin(), aftn.end());
	for (int i = 1; i < aftn.size(); i++) {
		int rep = aftn[i]-aftn[i-1]-1;
		int ops = aftn.size() - i;
		//cout << "here: " << aftn[i] << " rep, ops: " << rep << " " << ops << endl;
		ans = (ans * 1LL * modpow(ops, rep))%mod;
	}

	return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:37:6: warning: unused variable 'maxv' [-Wunused-variable]
  int maxv = -1;
      ^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:84:6: warning: variable 'initialvals' set but not used [-Wunused-but-set-variable]
  int initialvals[n];
      ^~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:125:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < aftn.size(); i++) {
                  ~~^~~~~~~~~~~~~

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