# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
64730 |
2018-08-05T13:22:01 Z |
FLDutchman |
Towns (IOI15_towns) |
C++14 |
|
44 ms |
660 KB |
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
#define fst first
#define snd second
#define LSB(k) k&-k
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int mod = 1e9+7;
int D;
INT hubDistance(INT N, INT sub) {
ii far = {-1, -1};
FOR(i, 1, N) far = max({getDistance(0, i), i}, far);
vi d1, d2;
int I = far.snd;
far = {-1, -1};
FOR(i, 0, N) {
if(i == I) d1.pb(0);
else d1.pb(getDistance(I, i)), far = max(far, {d1.back(), i});
}
int J = far.snd;
D = far.fst;
FOR(i, 0, N){
if(i == J) d2.pb(0);
else d2.pb(getDistance(J, i));
}
int R = 1e9;
map<int, int> cnt;
FOR(i, 0, N){
int d = (d1[i] + d2[i] - D)/2;
cnt[d1[i]-d]++;
R = min(R, max(d1[i]-d, d2[i]-d));
}
int r2 = D - R;
// amnt < R, = R, > R
int l = 0, e = 0, g = 0;
int L = 0, E = 0, G = 0;
for(auto it : cnt){
if(cnt[R] != 0){
if(it.fst < R) l += it.snd;
if(it.fst == R) e += it.snd;
if(it.fst > R) g += it.snd;
}
if(cnt[r2] != 0){
if(it.fst < r2) L += it.snd;
if(it.fst == r2) E += it.snd;
if(it.fst > r2) G += it.snd;
}
}
if(max(l, max(e, g)) > N/2) R *= -1;
if(max(L, max(E, G)) > N/2 and R >= 0) R *= -1;
return R;
}
Compilation message
towns.cpp: In function 'INT hubDistance(INT, INT)':
towns.cpp:24:42: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
FOR(i, 1, N) far = max({getDistance(0, i), i}, far);
^
towns.cpp:30:30: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
else d1.pb(getDistance(I, i)), far = max(far, {d1.back(), i});
^
towns.cpp:30:30: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
towns.cpp:36:30: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
else d2.pb(getDistance(J, i));
^
towns.cpp:36:30: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
towns.cpp:63:9: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
return R;
^
towns.cpp:22:28: warning: unused parameter 'sub' [-Wunused-parameter]
INT hubDistance(INT N, INT sub) {
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
376 KB |
Output is correct |
2 |
Correct |
18 ms |
376 KB |
Output is correct |
3 |
Correct |
4 ms |
376 KB |
Output is correct |
4 |
Correct |
26 ms |
408 KB |
Output is correct |
5 |
Correct |
22 ms |
408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
584 KB |
Output is correct |
2 |
Correct |
19 ms |
584 KB |
Output is correct |
3 |
Correct |
27 ms |
660 KB |
Output is correct |
4 |
Correct |
29 ms |
660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
660 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
660 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
37 ms |
660 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |