#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <functional>
#include "libmean.h"
using namespace std;
typedef long long llong;
int n;
int A[101];
int query(int a, int b, int c, int d) {
static map<int, int> ret;
vector<int> v;
v.push_back(a);
v.push_back(b);
v.push_back(c);
v.push_back(d);
sort(v.begin(), v.end());
int h = v[0] * 1000000 + v[1] * 10000 + v[2] * 100 + v[3];
if (ret.count(h)) return ret[h];
return ret[h] = Meandian(a, b, c, d);
}
template <class T>
vector<int> get_min_2(T cmp) {
int a = 1, b = 2, c = 3, d = 4, v = query(1, 2, 3, 4);
for (int i = 5; i <= n; ++i) {
int e = i;
swap(a, e);
if (cmp(query(a, b, c, d), v)) v = query(a, b, c, d);
else swap(a, e);
swap(b, e);
if (cmp(query(a, b, c, d), v)) v = query(a, b, c, d);
else swap(b, e);
swap(c, e);
if (cmp(query(a, b, c, d), v)) v = query(a, b, c, d);
else swap(c, e);
swap(d, e);
if (cmp(query(a, b, c, d), v)) v = query(a, b, c, d);
else swap(d, e);
}
int e;
for (e = 1; e <= n; ++e) {
if (e == a) continue;
if (e == b) continue;
if (e == c) continue;
if (e == d) continue;
break;
}
if (query(a, b, c, e) == v);
else if (query(a, b, e, d) == v) swap(c, d);
else if (query(a, e, c, d) == v) swap(b, d);
else swap(a, d);
if (query(a, b, e, d) == query(a, e, c, d)) swap(a, c);
else if (query(a, b, e, d) == query(e, b, c, d)) swap(b, c);
return { a, b };
}
int S[101];
int main() {
n = Init();
for (int i = 1; i <= n; ++i) A[i] = -1;
if (n > 4) {
vector<int> min2 = get_min_2(less<int>());
vector<int> max2 = get_min_2(greater<int>());
vector<int> etc;
int mn = min2[0], mx = max2[0];
for (int i = 1; i <= n; ++i) {
if (mn == i) continue;
if (mx == i) continue;
etc.push_back(i);
}
llong sum = 0;
for (int i = 0; i < etc.size(); ++i) {
int j = (i + 1) % etc.size();
sum += S[i] = query(etc[i], etc[j], mn, mx);
}
for (int i = 0; i < etc.size(); ++i) {
int l = (i + etc.size() - 1) % etc.size();
int r = (i + 1) % etc.size();
llong tsum = sum - S[i] - S[l];
tsum += query(etc[l], etc[r], mn, mx);
A[etc[i]] = sum - tsum;
}
A[min2[1]] = -1;
A[max2[1]] = -1;
}
Solution(A + 1);
return 0;
}
Compilation message
meandian.cpp: In function 'int main()':
meandian.cpp:77:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < etc.size(); ++i) {
~~^~~~~~~~~~~~
meandian.cpp:81:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < etc.size(); ++i) {
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
424 KB |
Output is correct |
| 4 |
Correct |
3 ms |
316 KB |
Output is correct |
| 5 |
Correct |
3 ms |
312 KB |
Output is correct |
| 6 |
Correct |
6 ms |
248 KB |
Output is correct |
| 7 |
Correct |
8 ms |
376 KB |
Output is correct |
| 8 |
Correct |
7 ms |
320 KB |
Output is correct |
| 9 |
Correct |
7 ms |
316 KB |
Output is correct |
| 10 |
Correct |
13 ms |
444 KB |
Output is correct |
