oj.uz

Submission #125116

# Submission time Handle Problem Language Result Execution time Memory
125116 2019-07-04T16:04:21 Z khulegub Gondola (IOI14_gondola) C++14
55 / 100
 23 ms 2528 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
using namespace std;
typedef long long i64;
typedef pair<int, int> pii;
 
 
 
 
int valid(int n, int arr[]){
	vector<pii> rep;
	vector<pii> v;
	for (int i = 0; i < n; i++){
		arr[i]--;
		// cout << arr[i] << ' ';
		if (arr[i] >= n){
			rep.pb(mp(arr[i] - n, i) );
		}
		else v.pb(mp(i, arr[i]) );
	}
	if(v.size() > 0){
		int diff = v[0].yy - v[0].xx;
		int end = (n - 1) - diff;
		int diff2 = diff - n;
		// cout << diff2;
		int vn = v.size();
		for (int i = 0; i < vn; i++){
			if (v[i].xx <= end){
				if (v[i].yy - v[i].xx != diff) return 0;
			}
			else{
				if (v[i].yy - v[i].xx != diff2) return 0;
			}
		}
	}
	sort(rep.begin(), rep.end());
	for(int i = 0; i + 1 < rep.size(); i++){
		if(rep[i].xx == rep[i + 1].xx) return 0;
	}
	// cout << "veve";
	return 1;
}
//----------------------
 
int replacement(int n, int arr[], int repl[]){
	vector<pii> rep;
	vector<pii> v;
	for (int i = 0; i < n; i++){
		arr[i]--;
		if (arr[i] >= n){
			rep.pb( mp(arr[i] - n, i) );
		}
		else {
			v.pb( mp(i, arr[i]) );
		}
	}
	sort(rep.begin(), rep.end() );
	if(v.size() > 0){
		int diff = v[0].yy - v[0].xx;
		int end = (n - 1) - diff;
		int diff2 = diff - n;
		int repsz = 0;
		int last = 0;
		for(int i = 0; i < rep.size(); i++){
			for(int j = last; j <= rep[i].xx; j++){
				int tmp;
				if(j == last){
					if(rep[i].yy <= end) tmp = rep[i].yy + diff;
					else tmp = rep[i].yy + diff2;
				}
				else{
					tmp = n + j - 1;
				}
				tmp++;
				repl[j] = tmp;
				repsz++;
			}
			last = rep[i].xx + 1;
		}
		return repsz;
		// cout << diff2;
	}
	else{ //wtf evdreegu neg ch bdggu nasss
		int repsz = 0;
		int last = 0;
		for(int i = 0; i < rep.size(); i++){
			for(int j = last; j <= rep[i].xx; j++){
				int tmp;
				if(j == last){
					tmp = rep[i].yy;
				}
				else{
					tmp = n + j - 1;
				}
				tmp++;
				// cout << tmp << ' ';
				repl[j] = tmp;
				repsz++;
			}
			last = rep[i].xx + 1;
		}
		return repsz;
	}
}
 
//----------------------
 
int countReplacement(int n, int inputSeq[])
{
  return -3;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i + 1 < rep.size(); i++){
                 ~~~~~~^~~~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < rep.size(); i++){
                  ~~^~~~~~~~~~~~
gondola.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < rep.size(); i++){
                  ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 7 ms 1268 KB Output is correct
7 Correct 15 ms 2288 KB Output is correct
8 Correct 12 ms 2132 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 14 ms 2288 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 8 ms 1396 KB Output is correct
7 Correct 15 ms 2288 KB Output is correct
8 Correct 13 ms 2156 KB Output is correct
9 Correct 5 ms 888 KB Output is correct
10 Correct 14 ms 2304 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 8 ms 1392 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 16 ms 2160 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 404 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 13 ms 2288 KB Output is correct
12 Correct 15 ms 2288 KB Output is correct
13 Correct 18 ms 1536 KB Output is correct
14 Correct 13 ms 2288 KB Output is correct
15 Correct 23 ms 2528 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 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 376 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 256 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 256 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -