oj.uz

Submission #902815

# Submission time Handle Problem Language Result Execution time Memory
902815 2024-01-11T03:14:39 Z Muhammad_Aneeq Gondola (IOI14_gondola) C++17
35 / 100
 1000 ms 6536 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include "gondola.h"
using namespace std;
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<s.size()-1;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=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];
		}
	}
	set<int>s;
	for (auto i:f)
		s.insert(i);
	int req=(ind+n+1-val)%n;
	d={};
	for (int i=1;i<=n;i++)
	{
		d[req++]=i;
		req%=n;
	}
	vector<pair<int,int>>w;
	for (int i=0;i<n;i++)
		w.push_back({gondolaSeq[i],i});
	sort(begin(w),end(w));
	int g=0;
	for (int k=0;k<n;k++)
	{
		int i=d[w[k].second];
		int req=w[k].second;
		auto x=s.lower_bound(i);
		if (x==s.end()||*x!=i)
			continue;
		vector<int>e;
		while (x!=s.end()&&(*x)<=gondolaSeq[req])
		{
			if (*x==i||*x>n)
			{
				replacementSeq[g++]=*x;
				e.push_back(*x);
			}
			x++;
		}
		for (auto j:e)
			s.erase(j);
	}
	return f.size();
}
int countReplacement(int n, int inputSeq[])
{
	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 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 348 KB Output is correct

Subtask #2
5.0 / 5.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 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 356 KB Output is correct
6 Correct 8 ms 2436 KB Output is correct
7 Correct 32 ms 4304 KB Output is correct
8 Correct 16 ms 4800 KB Output is correct
9 Correct 6 ms 1752 KB Output is correct
10 Correct 19 ms 5460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 8 ms 2520 KB Output is correct
7 Correct 21 ms 4308 KB Output is correct
8 Correct 16 ms 4660 KB Output is correct
9 Correct 5 ms 1752 KB Output is correct
10 Correct 18 ms 5340 KB Output is correct
11 Correct 0 ms 612 KB Output is correct
12 Correct 0 ms 360 KB Output is correct
13 Correct 12 ms 2152 KB Output is correct
14 Correct 1 ms 360 KB Output is correct
15 Correct 28 ms 5344 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 43 ms 5580 KB Output is correct
12 Correct 48 ms 6156 KB Output is correct
13 Execution timed out 1078 ms 6536 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -