/*
CEOI 2006
Competition Day #2
Task MEANDIAN
Sample library for C/C++
*/
/*
input file format:
N
a1 a2 ... aN
*/
#include <bits/stdc++.h>
#include "libmean.h"
using namespace std;
const int INF = 1e9;
const int MAXN = 100;
int sol[MAXN];
inline int get(vector <int> a) {
bool ok = 1;
int i = 0;
while(ok) {
ok = 0, i++;
for(auto it : a) {
if(it == i) {
ok = 1;
}
}
}
return i;
}
inline void del(vector <int> &a, int x) {
vector <int> aux;
for(auto it : a) {
if(it != x) aux.push_back(it);
}
swap(a, aux);
}
int main() {
int n, i, j;
n = Init();
vector <int> a = {1, 2, 3, 4};
vector <int> b = a;
int mn = Meandian(a[0], a[1], a[2], a[3]);
int mx = mn;
for(i = 5; i <= n; i++) {
vector <int> aux = a;
for(j = 0; j < 4; j++) {
vector <int> cur;
for(int k = 0; k < 4; k++) {
cur.push_back(k != j ? a[k] : i);
}
int val = Meandian(cur[0], cur[1], cur[2], cur[3]);
if(val < mn) {
mn = val, aux = cur;
}
}
a = aux;
aux = b;
for(j = 0; j < 4; j++) {
vector <int> cur;
for(int k = 0; k < 4; k++) {
cur.push_back(k != j ? b[k] : i);
}
int val = Meandian(cur[0], cur[1], cur[2], cur[3]);
if(val > mx) {
mx = val, aux = cur;
}
}
b = aux;
}
memset(sol, -1, sizeof(sol));
if(n == 4) { Solution(sol); return 0; }
int id_mn4, ga = get(a);
mn = INF;
for(i = 0; i < 4; i++) {
vector <int> cur;
for(j = 0; j < 4; j++) {
cur.push_back(i != j ? a[j] : ga);
}
int val = Meandian(cur[0], cur[1], cur[2], cur[3]);
if(val < mn) {
mn = val, id_mn4 = a[i];
}
}
del(a, id_mn4);
int id_mx4, gb = get(b);
mx = 0;
for(i = 0; i < 4; i++) {
vector <int> cur;
for(j = 0; j < 4; j++) {
cur.push_back(i != j ? b[j] : gb);
}
int val = Meandian(cur[0], cur[1], cur[2], cur[3]);
if(val > mx) {
mx = val, id_mx4 = b[i];
}
}
del(b, id_mx4);
int id_mn3; mn = INF;
for(i = 0; i < 3; i++) {
for(j = i + 1; j < 3; j++) {
int val = Meandian(a[i], a[j], ga, id_mn4);
if(val < mn) {
mn = val, id_mn3 = a[3 - i - j];
}
}
}
del(a, id_mn3);
int id_mx3; mx = 0;
for(i = 0; i < 3; i++) {
for(j = i + 1; j < 3; j++) {
int val = Meandian(b[i], b[j], gb, id_mx4);
if(val > mx) {
mx = val, id_mx3 = b[3 - i - j];
}
}
}
del(b, id_mx3);
vector <bool> vis(n + 1, 1);
vis[a[0]] = vis[a[1]] = vis[b[0]] = vis[b[1]] = 0;
vector <int> ids;
for(i = 1; i <= n; i++) {
if(vis[i]) ids.push_back(i);
}
int x = 2 * Meandian(a[0], a[1], b[0], b[1]);
int y = 2 * Meandian(a[0], a[1], ids[0], b[0]);
int z = 2 * Meandian(b[0], b[1], ids[0], a[0]);
sol[ids[0] - 1] = (y + z - x) / 2;
for(i = 1; i < ids.size(); i++) {
sol[ids[i] - 1] = 2 * Meandian(a[0], b[0], ids[0], ids[i]) - sol[ids[0] - 1];
//cerr << ids[i] << " " << a[0] << " " << b[0] << " " << ids[0] << "\n";
}
Solution(sol);
return 0;
}
Compilation message
meandian.cpp: In function 'int main()':
meandian.cpp:148:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 1; i < ids.size(); i++) {
~~^~~~~~~~~~~~
meandian.cpp:133:8: warning: 'id_mx3' may be used uninitialized in this function [-Wmaybe-uninitialized]
del(b, id_mx3);
~~~^~~~~~~~~~~
meandian.cpp:122:8: warning: 'id_mn3' may be used uninitialized in this function [-Wmaybe-uninitialized]
del(a, id_mn3);
~~~^~~~~~~~~~~
meandian.cpp:111:8: warning: 'id_mx4' may be used uninitialized in this function [-Wmaybe-uninitialized]
del(b, id_mx4);
~~~^~~~~~~~~~~
meandian.cpp:97:8: warning: 'id_mn4' may be used uninitialized in this function [-Wmaybe-uninitialized]
del(a, id_mn4);
~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
4 ms |
248 KB |
Output is correct |
| 4 |
Correct |
4 ms |
248 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
7 ms |
376 KB |
Output is correct |
| 8 |
Correct |
10 ms |
248 KB |
Output is correct |
| 9 |
Correct |
14 ms |
376 KB |
Output is correct |
| 10 |
Correct |
12 ms |
376 KB |
Output is correct |
