Submission #60817

#	Time	Username	Problem	Language	Result	Execution time	Memory
60817		hamzqq9	Gondola (IOI14_gondola)	C++14	100 / 100	127 ms	15688 KiB

gondola

#include "gondola.h"
#define st first
#define nd second
#define ii pair<int,int> 
#define pb push_back
#define sz(x) (x.size())
#include<bits/stdc++.h>
using namespace std;

int find_fixed(int n,int inputSeq[]) {

	int fixed=0;

	for(int i=0;i<n;i++) {

		if(inputSeq[i]<=n) {

			fixed=i;

			break ;

		}

	}

	return fixed;

}

int valid(int n, int inputSeq[]) {

	map<int,int> fr;

	int fixed=find_fixed(n,inputSeq);

	int tot=2;

	int cur=inputSeq[fixed];

	for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) {

		if(cur>n) cur-=n;

		if(inputSeq[i]>n) {
		
			fr[inputSeq[i]]++;

			continue ;
		
		}

		if(inputSeq[i]!=cur) return 0;

	}

	for(auto x:fr) {

		if(x.nd>1) return 0;

	}

	return 1;

}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {

	int fixed=find_fixed(n,gondolaSeq);

	int cur=(gondolaSeq[fixed]<=n?gondolaSeq[fixed]:1);
	int tot=2;

	vector<ii> change;

	for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) {

		if(cur>n) cur-=n;

		if(gondolaSeq[i]>n) {

			change.pb({gondolaSeq[i],cur});

		}

	}

	sort(change.begin(),change.end());

	int sz=0;
	int val=n;

	for(int i=0;i<sz(change);i++) {

		auto x=change[i];

		replacementSeq[sz++]=x.nd;

		val++;

		while(val<x.st) {

			replacementSeq[sz++]=val++;

		}

	}

	return sz;

}
#define MOD 1000000009
//----------------------

int fe(int x,int y) {

	if(y==0) return 1;
	if(y==1) return x;

	int res=fe(x,y/2);

	res=1ll*res*res%MOD;

	if(y&1) return 1ll*res*x%MOD;

	return res;

}

int countReplacement(int n, int inputSeq[]) {

	int isvalid=valid(n,inputSeq);

	vector<int> ranges;

	if(!isvalid) return 0;

	for(int i=0;i<n;i++) {

		if(inputSeq[i]<=n) continue ;

		ranges.pb(inputSeq[i]);

	}
	
	int ans=(sz(ranges)==n?n:1);

	ranges.pb(n);

	sort(ranges.begin(),ranges.end());

	int cursz=sz(ranges)-1;

	for(int i=1;i<sz(ranges);i++,cursz--) {

		int range=ranges[i]-ranges[i-1]-1;

		ans=1ll*ans*fe(cursz,range)%MOD;

	}

	return ans;

}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<sz(change);i++) {
               ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:147:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int ans=(sz(ranges)==n?n:1);
                     ^
gondola.cpp:155:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<sz(ranges);i++,cursz--) {
               ^

• 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