Submission #833172

#	Time	Username	Problem	Language	Result	Execution time	Memory
833172		Halym2007	Gondola (IOI14_gondola)	C++11	100 / 100	50 ms	6980 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define sz size()
#define pb push_back
#define ll long long
map <int, bool> m;

ll md = 1e9 + 9;

int valid(int n, int inputSeq[]) {
	int ind = -1;
	for (int i = 0; i < n; ++i) {
		if (m[inputSeq[i]]) return 0;
		m[inputSeq[i]] = 1;
	}
	for (int i = 0; i < n; ++i) {
		if (inputSeq[i] <= n) {
			ind = i;
			break;
		}
	}
	if (ind == -1) return 1;
	int val = inputSeq[ind] - 1;
	for (int i = 0; i < n; ++i) {
		if (inputSeq[ind] <= n and (val + 1) != inputSeq[ind]) {
			return 0;
		}
		ind++;
		val++;
		ind %= n;
		val %= n;
	}
	return 1;
}

int replacement(int n, int arr[], int rep[]) {
	int mx = -1, mn = 1e9;
	for (int i = 0; i < n; ++i) {
		mx = max(mx, arr[i]);
		mn = min (mn, arr[i]);
	}
	int o = 0;
	if (mx <= n) 
		return 0;
	vector <int> orig(n, 0);
	if (mn > n) {
		for (int i = 0; i < n; ++i) {
			orig[i] = i + 1;
		}
	} 
	else {
		int pos;
		for (int i = 0; i < n; ++i) {
			if (arr[i] <= n) {
				pos = i;
				break;
			}
		}
		int val = arr[pos];
		for (int i = 0; i < n; ++i) {
			orig[pos] = val;
			pos++;
			val++;
			if (val > n) val = 1;
			if (pos == n) pos = 0;
		}
	}
	vector <int> idx;
	for (int i = 0; i < n; ++i) {
		if (arr[i] > n) {
			idx.pb (i);
		}
	}
	sort (idx.begin(), idx.end(), [&] (int x, int y) {
		return (arr[x] < arr[y]);	
	});
	int last = n + 1;
	for (int i = 0; i < (int)idx.sz; ++i) {
		rep[o++] = orig[idx[i]];
		
		while (last < arr[idx[i]]) {
			rep[o++] = last++;
		}
		last++;
	}
	return o;
}


ll solve (int x, int y) {
	if (y == 0) return 1;
	ll jp = solve (x, y / 2); 
	jp *= jp;
	jp %= md;
	if (y % 2 == 1) {
		jp *= x;
		jp %= md;
	}
	return jp;
}


int countReplacement(int n, int arr[]) {
	if (!valid(n, arr)) {
		return 0;
	}
	int mx = 0, mn = 1e9;
	for (int i = 0; i < n; ++i) {
		mx = max(mx, arr[i]);
		mn = min (mn, arr[i]);
	}
	int o = 0;
	if (mx <= n) 
		return 1;
	vector <int> orig(n, 0);
	if (mn > n) {
		for (int i = 0; i < n; ++i) {
			orig[i] = i + 1;
		}
	} 
	else {
		int pos;
		for (int i = 0; i < n; ++i) {
			if (arr[i] <= n) {
				pos = i;
				break;
			}
		}
		int val = arr[pos];
		for (int i = 0; i < n; ++i) {
			orig[pos] = val;
			pos++;
			val++;
			if (val > n) val = 1;
			if (pos == n) pos = 0;
		}
	}
	vector <int> idx;
	for (int i = 0; i < n; ++i) {
		if (arr[i] > n) {
			idx.pb (i);
		}
	}
	sort (idx.begin(), idx.end(), [&] (int x, int y) {
		return (arr[x] < arr[y]);	
	});
	ll jogap = 1;
	if (mn > n) jogap = n;
	int last = n + 1;
	for (int i = 0; i < (int)idx.sz; ++i) {
		ll jj = idx.sz - i;
		ll ii = (arr[idx[i]]-1) - last + 1;
		ll kp = solve (jj, ii);
		if (kp == 0) kp = 1;
		jogap *= kp;
//		jogap *= (ii * jj) % md;
		jogap %= md;
		last = arr[idx[i]] + 1;
	}
	return jogap;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:113:6: warning: unused variable 'o' [-Wunused-variable]
  113 |  int o = 0;
      |      ^
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:60:17: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |   int val = arr[pos];
      |                 ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:130:17: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  130 |   int val = arr[pos];
      |                 ^~~

• 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