| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 235745 |
2020-05-29T14:48:36 Z |
ryansee |
Towns (IOI15_towns) |
C++14 |
|
30 ms |
512 KB |
#include "towns.h"
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
using ll=long long;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>;
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
int hubDistance(int n, int sub) {
ll q=0;
vector<vector<ll>> memo;
memo.resize(n, vector<ll>(n, -1));
auto ask=[&](ll x,ll y){
if(x==y)return 0ll;
if(x>y)swap(x,y);
q+=memo[x][y]==-1;
assert(q<=n*(n+1)/2);
if(~memo[x][y]) return memo[x][y];
return memo[x][y]=ll(getDistance(x,y));
};
ll e1=0, e2=0;
FOR(i,0,n-1) {
if(ask(0, i) > ask(0, e1))e1=e2=i;
}
FOR(i,0,n-1) {
if(ask(e1, i) > ask(e1, e2))e2=i;
}
cerr<<q<<'\n';
ll diam=ask(e1,e2);
// cerr<<e1<<' '<<e2<<' '<<diam<<'\n';
ll r=LLINF;
vector<ll> dist_fromb;
vector<ll> dist(n,0);
FOR(i,0,n-1){
ll own=(ask(e1,0)+ask(e1,i)-ask(0,i))/2;
dist[i]=own;
if(max(own,diam-own)<r) {
dist_fromb.clear();
dist_fromb.eb(own);
r=max(own,diam-own);
}else if(max(own,diam-own)==r) {
dist_fromb.eb(own);
}
}
cerr<<q<<'\n';
sort(all(dist_fromb));
dist_fromb.resize(unique(all(dist_fromb))-dist_fromb.begin());
assert(dist_fromb.size() == 1 || dist_fromb.size() == 2);
if(dist_fromb.size() == 2){
ll crit=dist[e2], co=0;
assert(dist[0]>=crit);
FOR(i,0,n-1)if(dist[i]>=crit){
assert(i^e1);
++ co;
}
if(co <= n/2) {
dist_fromb.pop_back();
} else {
dist_fromb.erase(dist_fromb.begin());
}
}
ll cent=dist_fromb[0];
// cerr<<"cent: "<<cent<<'\n';
auto same=[&](ll x,ll y){
return (ask(e1,x)+ask(e1,y)-ask(x,y))/2 != cent && ((dist[x] >= cent) == (dist[y] >= cent));
};
// FOR(i,0,n-1)FOR(j,i+1,n-1){
// cerr<<i<<' '<<j<<": "<<same(i,j)<<'\n';
// }
vector<ll>last,bin;//all in bin at one point of time, are of same type
FOR(i,0,n-1) {
if(last.empty() || !same(last.back(), i)) {
last.eb(i);
if(bin.size()) {
last.eb(bin.back());
bin.pop_back();
}
}else {
bin.eb(i);
}
}
ll M=last.back(), sz=1+bin.size(); // a representative of the majority!!!!
// all those in bin, are part of majority
for(ll i=siz(last)-3; i>=0; --i) {
if(same(last[i], M)){
++ sz;
-- i;
}
}
cerr<<q<<'\n';
// cerr<<"sz: "<<sz<<'\n';
if(sz > n/2) r *= -1;
return r;
}
Compilation message
towns.cpp: In lambda function:
towns.cpp:41:39: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return memo[x][y]=ll(getDistance(x,y));
^
towns.cpp:41:39: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:115:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return r;
^
towns.cpp:31:28: warning: unused parameter 'sub' [-Wunused-parameter]
int hubDistance(int n, int sub) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
512 KB |
Output is correct |
| 2 |
Correct |
21 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
30 ms |
512 KB |
Output is correct |
| 5 |
Correct |
27 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
