oj.uz

Submission #72913

# Submission time Handle Problem Language Result Execution time Memory
72913 2018-08-27T08:25:52 Z nvmdava Gondola (IOI14_gondola) C++17
55 / 100
 79 ms 5172 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
 
struct Gondola{
	int id, val;
	Gondola(int _id, int _val){
		id = _id;
		val = _val;
	}
	bool operator<(const Gondola& rhs) const{
		return val < rhs.val;
	}
};
 
int ord[100001];
map<int, int> in;
vector<Gondola> v;
 
 
int valid(int n, int inputSeq[]){
	int i;
	for(i = 0; i < n; i++){
		if(in[inputSeq[i]]) return 0;
		in[inputSeq[i]] = 1;
	}
	for(i = 0; i < n; i++){
		if(inputSeq[i] <= n) break;
	}
	if(i == n) return 1;
	int k = inputSeq[i] - 1;
	for(int j = 0; j < n; j++){
		ord[(k + j) % n] = inputSeq[(i + j) % n];
		if((ord[(k + j) % n] != (k + j) % n + 1 && ord[(k + j) % n] <= n) || ord[(k + j) % n] < 1) return 0;
	}
	for(i = 0; i < n; i++){
		if((ord[i] != i + 1 && ord[i] <= n) || ord[i] < 1) return 0;
	}
	return 1;
}
 
//----------------------
 
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	int i;
	for(i = 0; i < n; i++){
		if(gondolaSeq[i] <= n) break;
	}
	int k;
	if(i == n){
		i = 0;
		k = 0;
	} else {
		k = gondolaSeq[i] - 1;	
	}
	for(int j = 0; j < n; j++){
		v.push_back(Gondola((k + j) % n + 1, gondolaSeq[(i + j) % n]));
	}
	sort(v.begin(), v.end());
	i = 0;
	int s = n + 1;
	for(auto x : v){
		if(x.val <= n) continue;
		replacementSeq[i] = x.id;
		i++;
		for(; s < x.val; s++){
			replacementSeq[i] = s;
			i++;
		}
		s = x.val + 1;
	}
	return i;
}
 
//----------------------
 
int countReplacement(int n, int inputSeq[]){
	int i;
	for(i = 0; i < n; i++){
		if(inputSeq[i] <= n) break;
	}
	int k;
	if(i == n){
		i = 0;
		k = 0;
	} else {
		k = inputSeq[i] - 1;	
	}
	for(int j = 0; j < n; j++){
		ord[(k + j) % n] = inputSeq[(i + j) % n];
	}
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:92:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 612 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 612 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 28 ms 2668 KB Output is correct
7 Correct 18 ms 2668 KB Output is correct
8 Correct 35 ms 4464 KB Output is correct
9 Correct 17 ms 4464 KB Output is correct
10 Correct 49 ms 5100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 2 ms 5100 KB Output is correct
4 Correct 3 ms 5100 KB Output is correct
5 Correct 2 ms 5100 KB Output is correct
6 Correct 28 ms 5100 KB Output is correct
7 Correct 20 ms 5100 KB Output is correct
8 Correct 36 ms 5100 KB Output is correct
9 Correct 12 ms 5100 KB Output is correct
10 Correct 51 ms 5172 KB Output is correct
11 Correct 2 ms 5172 KB Output is correct
12 Correct 3 ms 5172 KB Output is correct
13 Correct 33 ms 5172 KB Output is correct
14 Correct 3 ms 5172 KB Output is correct
15 Correct 79 ms 5172 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5172 KB Output is correct
2 Correct 2 ms 5172 KB Output is correct
3 Correct 2 ms 5172 KB Output is correct
4 Correct 2 ms 5172 KB Output is correct
5 Correct 3 ms 5172 KB Output is correct
6 Correct 3 ms 5172 KB Output is correct
7 Correct 2 ms 5172 KB Output is correct
8 Correct 3 ms 5172 KB Output is correct
9 Correct 3 ms 5172 KB Output is correct
10 Correct 3 ms 5172 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5172 KB Output is correct
2 Correct 3 ms 5172 KB Output is correct
3 Correct 2 ms 5172 KB Output is correct
4 Correct 2 ms 5172 KB Output is correct
5 Correct 3 ms 5172 KB Output is correct
6 Correct 2 ms 5172 KB Output is correct
7 Correct 3 ms 5172 KB Output is correct
8 Correct 4 ms 5172 KB Output is correct
9 Correct 4 ms 5172 KB Output is correct
10 Correct 4 ms 5172 KB Output is correct
11 Correct 24 ms 5172 KB Output is correct
12 Correct 36 ms 5172 KB Output is correct
13 Correct 28 ms 5172 KB Output is correct
14 Correct 26 ms 5172 KB Output is correct
15 Correct 27 ms 5172 KB Output is correct

Subtask #7
0 / 5.0

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

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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