oj.uz

Submission #903414

# Submission time Handle Problem Language Result Execution time Memory
903414 2024-01-11T07:37:01 Z Muhammad_Aneeq Gondola (IOI14_gondola) C++17
100 / 100
 58 ms 10588 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include "gondola.h"
using namespace std;
int mod=1e9+9;
long long power(long long x,long long y)
{
	long long res=1;
	while (y>0)
	{
		if (y%2)
			res=(res*x)%mod;
		x=(x*x)%mod;
		y/=2;
	}
	return res;
}
int valid(int n, int inputSeq[])
{
	vector<pair<int,int>>s={};
	map<int,int>d;
	for (int i=0;i<n;i++)
	{
		d[inputSeq[i]]++;
		if (inputSeq[i]<=n)
			s.push_back({inputSeq[i],i});
	}
	for (auto i:d)
	{
		if (i.second>1)
			return 0;
	}
	for (int i=0;i+1<s.size();i++)
	{
		int z=s[i+1].second-s[i].second;
		if (((s[i+1].first-z+n-1)%n)+1==s[i].first)
			continue;
		return 0;
	}	
	return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int z=0;
	map<int,int>d;
	for (int i=0;i<n;i++)	
	{
		d[gondolaSeq[i]]++;
		z=max(z,gondolaSeq[i]);
	}
	vector<int>f;
	for (int i=n+1;i<z;i++)
	{
		if (d.find(i)==d.end())
			f.push_back(i);
		else
			if (d[i]>1)
				return 0;
	}
	int ind=0,val=1;
	for (int i=0;i<n;i++)
	{
		if (gondolaSeq[i]<=n)
		{
			ind=i;
			val=gondolaSeq[i];
		}
	}
	int req=(ind+n+1-val)%n;
	vector<pair<int,int>>w;
	for (int i=0;i<n;i++)
		w.push_back({gondolaSeq[i],i});
	sort(begin(w),end(w));
	map<int,int>in;
	for (int i=1;i<=n;i++)
	{
		in[req++]=i;
		req%=n;
	}
	int g=0;
	reverse(begin(f),end(f));
	for (int i=0;i<n;i++)
	{
		if (d[in[w[i].second]]==0)
		{
			replacementSeq[g++]=in[w[i].second];
		}
		while (f.size()&&f.back()<w[i].first)
		{
			replacementSeq[g++]=f.back();
			f.pop_back();
		}
	}
	return g;
}
int countReplacement(int n, int inputSeq[])
{
	if (!valid(n,inputSeq))
		return 0;
	vector<int>s;
	for (int i=0;i<n;i++)
	{
		if (inputSeq[i]>n)
			s.push_back(inputSeq[i]);
	}
	s.push_back(n);
	sort(begin(s),end(s));
	long long ans=power(n,(s.size()==n+1));
	for (int i=1;i<s.size();i++)
		ans=(ans*power(s.size()-i,s[i]-s[i-1]-1))%mod;
	return (int)(ans);
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i=0;i+1<s.size();i++)
      |               ~~~^~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:111:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |  long long ans=power(n,(s.size()==n+1));
      |                         ~~~~~~~~^~~~~
gondola.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (int i=1;i<s.size();i++)
      |               ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 8 ms 2728 KB Output is correct
7 Correct 21 ms 4828 KB Output is correct
8 Correct 15 ms 5360 KB Output is correct
9 Correct 5 ms 1752 KB Output is correct
10 Correct 18 ms 5584 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 12 ms 2772 KB Output is correct
7 Correct 32 ms 4772 KB Output is correct
8 Correct 16 ms 5072 KB Output is correct
9 Correct 5 ms 1752 KB Output is correct
10 Correct 17 ms 5584 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 17 ms 2392 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 41 ms 5820 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 1 ms 360 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 360 KB Output is correct
11 Correct 41 ms 9172 KB Output is correct
12 Correct 58 ms 10588 KB Output is correct
13 Correct 44 ms 6148 KB Output is correct
14 Correct 42 ms 8924 KB Output is correct
15 Correct 36 ms 4716 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 28 ms 4764 KB Output is correct
10 Correct 22 ms 4052 KB Output is correct
11 Correct 9 ms 1732 KB Output is correct
12 Correct 15 ms 2020 KB Output is correct
13 Correct 3 ms 604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 30 ms 4616 KB Output is correct
10 Correct 23 ms 4052 KB Output is correct
11 Correct 9 ms 1624 KB Output is correct
12 Correct 11 ms 1900 KB Output is correct
13 Correct 2 ms 600 KB Output is correct
14 Correct 36 ms 5460 KB Output is correct
15 Correct 46 ms 5972 KB Output is correct
16 Correct 10 ms 1372 KB Output is correct
17 Correct 32 ms 4188 KB Output is correct
18 Correct 19 ms 2396 KB Output is correct