Submission #737588

#	Time	Username	Problem	Language	Result	Execution time	Memory
737588		esomer	곤돌라 (IOI14_gondola)	C++17	10 / 100	9 ms	1468 KiB

gondola

#include<bits/stdc++.h>
#include "gondola.h"
 
using namespace std;

const int MOD = 1e9 + 7;

long long pw(int a, int b){
	if(b == 0) return 1;
	if(b % 2 == 0){
		long long x = pw(a / 2, b);
		return (x * x) % MOD;
	}else{
		long long x = pw(a / 2, b);
		x = (x * x) % MOD;
		return (x * a) % MOD;
	}
}

int valid(int n, int* inputSeq){
	vector<int> cnt(n+1, 0);
	int mn = 1e9;
	int ind;
	for(int i = 0; i < n; i++){
		if(mn > inputSeq[i]){
			mn = inputSeq[i];
			ind = i;
		}
		cnt[inputSeq[i]]++;
		if(cnt[inputSeq[i]] > 1) return 0; 
	}
	if(mn > n) return 1;
	int lst = mn;
	for(int i = ind + 1; i % n != ind; i++){
		if(inputSeq[i % n] <= n){
			if(lst > inputSeq[i % n]) return 0;
			lst = inputSeq[i % n];
		}
	}
	return 1;
}

int replacement(int n, int* gondolaSeq, int* replacementSeq){
	int ind = 0;
	int add = 1e9;
	vector<pair<int, int>> v;
	for(int i = 0; i < n; i++){
		if(gondolaSeq[i] <= n && gondolaSeq[i] < add){
			add = gondolaSeq[i];
			ind = i;
		}
		if(gondolaSeq[i] > n){
			v.push_back({gondolaSeq[i], i});
		}
	}
	if(add == 1e9) add = 1;
	sort(v.begin(), v.end());
	int nxt = n + 1;
	int curr = 0;
	for(auto p : v){
		int initial;
		if(p.second < ind) initial = n - ind + p.second + add;
		else initial = p.second - ind + add;
		replacementSeq[curr] = initial; curr++;
		while(nxt != p.first){
			replacementSeq[curr] = nxt; nxt++; curr++;
		}
		nxt = p.first + 1;
	}
	return curr;
}

int countReplacement(int n, int* inputSeq){
	vector<int> cnt(n+1, 0);
	int mn = 1e9;
	int mx = 0;
	int ind;
	int broken = 0;
	vector<int> v;
	for(int i = 0; i < n; i++){
		if(mn > inputSeq[i]){
			mn = inputSeq[i];
			ind = i;
		}
		cnt[inputSeq[i]]++;
		if(cnt[inputSeq[i]] > 1) return 0; 
		mx = max(mx, inputSeq[i]); 
		if(inputSeq[i] > n) {broken++; v.push_back(inputSeq[i]);}
	}
	int lst = mn;
	for(int i = ind + 1; i % n != ind; i++){
		if(inputSeq[i % n] <= n){
			if(lst > inputSeq[i % n]) return 0;
			lst = inputSeq[i % n];
		}
	}
	long long ans = 1;
	lst = n;
	for(int x : v){
		ans *= pw(broken, x - lst); ans %= MOD;
		broken--; lst = x;
	}
	return (int)ans;
}

//~ int main(){
//~ }

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:34:29: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |  for(int i = ind + 1; i % n != ind; i++){
      |                       ~~~~~~^~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:91:10: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |  for(int i = ind + 1; i % n != ind; i++){
      |          ^

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