Submission #136307

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136307	2019-07-25T06:09:45 Z	김세빈(#3258)	Meandian (CEOI06_meandian)	C++14	90 / 100	7 ms	376 KB

meandian

#include <bits/stdc++.h>

#include "libmean.h"

using namespace std;

typedef pair <int, int> pii;

int A[111];
int n;

pii getidx(int i1, int i2, int i3, int i4, int i5, bool f)
{
	pii ret(-1, -1);
	int v1 = Meandian(i2, i3, i4, i5);
	int v2 = Meandian(i1, i3, i4, i5);
	int v3 = Meandian(i1, i2, i4, i5);
	int v4 = Meandian(i1, i2, i3, i5);
	int v5 = Meandian(i1, i2, i3, i4);
	int v = (f? min({v1, v2, v3, v4, v5}) : max({v1, v2, v3, v4, v5}));
	if(v == v1) (ret.first == -1? ret.first : ret.second) = i1;
	if(v == v2) (ret.first == -1? ret.first : ret.second) = i2;
	if(v == v3) (ret.first == -1? ret.first : ret.second) = i3;
	if(v == v4) (ret.first == -1? ret.first : ret.second) = i4;
	if(v == v5) (ret.first == -1? ret.first : ret.second) = i5;
	return ret;
}

pii find(bool f)
{
	vector <int> V;
	int m1, m2, i;
	
	m1 = 1; m2 = 2;
	
	for(i=5; i<=n; i+=3){
		tie(m1, m2) = getidx(m1, m2, i - 2, i - 1, i, f);
	}
	
	V.clear();
	
	for(i=n; V.size() < 3; i--){
		if(i != m1 && i != m2) V.push_back(i);
	}
	
	tie(m1, m2) = getidx(m1, m2, V[0], V[1], V[2], f);
	
	return pii(m1, m2);
}

void findval(vector <int> &V, int m1, int m2)
{
	int i, v;
	int v1 = Meandian(m1, m2, V[1], V[2]);
	int v2 = Meandian(m1, m2, V[0], V[2]);
	int v3 = Meandian(m1, m2, V[0], V[1]);
	int s = v1 + v2 + v3;
	
	A[V[0] - 1] = s - v1 * 2;
	A[V[1] - 1] = s - v2 * 2;
	A[V[2] - 1] = s - v3 * 2;
	
	for(i=3; i<V.size(); i++){
		A[V[i] - 1] = Meandian(m1, m2, V[0], V[i]) * 2 - A[V[0] - 1];
	}
}

int main()
{
	vector <int> V;
	int i, m1, m2, m3, m4;
	
	n = Init();
	
	for(i=1; i<=n; i++){
		A[i - 1] = -1;
	}
	
	if(n <= 4){
		Solution(A);
		return 0;
	}
	
	tie(m1, m2) = find(0); tie(m3, m4) = find(1);
	
	for(i=1; i<=n; i++){
		if(i != m1 && i != m2 && i != m3 && i != m4){
			V.push_back(i);
		}
	}
	
	findval(V, m1, m4);
	
	Solution(A);
	
	return 0;
}

Compilation message

meandian.cpp: In function 'void findval(std::vector<int>&, int, int)':
meandian.cpp:63:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=3; i<V.size(); i++){
           ~^~~~~~~~~
meandian.cpp:53:9: warning: unused variable 'v' [-Wunused-variable]
  int i, v;
         ^

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	248 KB	arguments must be between 1 and N
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	3 ms	248 KB	Output is correct
5	Correct	2 ms	248 KB	Output is correct
6	Correct	2 ms	296 KB	Output is correct
7	Correct	4 ms	248 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	6 ms	376 KB	Output is correct
10	Correct	7 ms	248 KB	Output is correct