oj.uz

Submission #51996

# Submission time Handle Problem Language Result Execution time Memory
51996 2018-06-23T03:09:35 Z zetapi Gondola (IOI14_gondola) C++14
35 / 100
 63 ms 5568 KB 
#include <gondola.h>
#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define ll long long
#define itr ::iterator 
 
typedef pair<int,int>  pii;
 
const int MAX=5e5;
 
int arr[MAX],fin[MAX],fre[MAX];

int valid(int n,int inputSeq[])
{
  	return 1;
}

int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
	vector<int> vec;
	priority_queue<int> absent;
	priority_queue<pii> present;
	pii cur;
	int N=n,mx=0,change=0,sec;
	for(int A=0;A<N;A++)
		arr[A]=A;
	for(int A=0;A<N;A++)
  	{
	  	if(gondolaSeq[A]<=N)
	  	{
			 gondolaSeq[A]--;
			 for(int B=A;B>=0;B--)
			 {
			 	arr[B]=gondolaSeq[A];
			 	gondolaSeq[A]--;
			 	if(gondolaSeq[A]<0)
			 		gondolaSeq[A]+=N;
			 }
			 gondolaSeq[A]=arr[A];
			 for(int B=A+1;B<N;B++)
			 {
			 	gondolaSeq[A]++;
			 	if(gondolaSeq[A]>=N)
			 		gondolaSeq[A]=0;
			 	arr[B]=gondolaSeq[A];
			 }
			 gondolaSeq[A]=arr[A]+1;
		 	 break;
		}
  	}
  	for(int A=0;A<N;A++)
  		arr[A]++;
  	for(int A=0;A<N;A++)
  	{
  		fre[gondolaSeq[A]]++;
  		mx=max(mx,gondolaSeq[A]);
  		present.push(mp(gondolaSeq[A],A));
  		if(arr[A]!=gondolaSeq[A])
  			change++;
  	}
  	for(int A=1;A<=mx;A++)
  	{
  		if(!fre[A])
  			absent.push(A);
  	}
  	while(!present.empty())
  	{
  		cur=present.top();
  		if(cur.first<=N+change)
  			break;
  		present.pop();
  		sec=absent.top();
  		present.push(mp(sec,cur.second));
  		absent.pop();
  		//cout<<cur.second<<" "<<cur.first<<" "<<sec<<"\n";
  		vec.pb(sec);
  	}
  	while(!present.empty())
  	{
  		cur=present.top();
  		present.pop();	
  		fin[cur.second]=cur.first;
  	}
  	for(int A=0;A<N;A++)
  	{
  		if(fin[A]!=arr[A])
  			present.push(mp(fin[A],arr[A]));
  	}
  	while(!present.empty())
  	{
  		cur=present.top();
  		present.pop();
  		vec.pb(cur.second);
  	}
  	reverse(vec.begin(),vec.end());
  //	for(auto A:vec)
  	//	cout<<A<<" ";
  	for(int A=0;A<vec.size();A++)
  		replacementSeq[A]=vec[A];
  	return vec.size();
}
  
int countReplacement(int n, int inputSeq[])
{
  	return -3;
}

/*int main()
{
	ios_base::sync_with_stdio(false);

	cout<<replacement()<<"\n";
	return 0;
}*/

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:101:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=0;A<vec.size();A++)
                ~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 3 ms 564 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 2 ms 572 KB Output is correct
5 Correct 3 ms 616 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 3 ms 628 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 3 ms 772 KB Output is correct
9 Correct 3 ms 772 KB Output is correct
10 Correct 4 ms 984 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 984 KB Output is correct
2 Correct 2 ms 984 KB Output is correct
3 Correct 2 ms 984 KB Output is correct
4 Correct 2 ms 984 KB Output is correct
5 Correct 2 ms 984 KB Output is correct
6 Correct 2 ms 984 KB Output is correct
7 Correct 2 ms 984 KB Output is correct
8 Correct 3 ms 984 KB Output is correct
9 Correct 3 ms 984 KB Output is correct
10 Correct 4 ms 992 KB Output is correct
11 Correct 30 ms 3292 KB Output is correct
12 Correct 27 ms 4080 KB Output is correct
13 Correct 38 ms 4132 KB Output is correct
14 Correct 22 ms 4468 KB Output is correct
15 Correct 63 ms 5568 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5568 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5568 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5568 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5568 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -