| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 794738 |
2023-07-26T21:11:11 Z |
fatemetmhr |
Towns (IOI15_towns) |
C++17 |
|
14 ms |
1108 KB |
// ~ Be Name Khoda ~ //
#include "towns.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 200;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
ll keep[maxn5][maxn5];
ll len[maxn5];
int n;
vector <int> av, tng, mesl;
ll gdis(int a, int b){
if(a == b)
return 0;
if(keep[a][b] != -1)
return keep[a][b];
return keep[a][b] = keep[b][a] = getDistance(a, b);
}
bool iden(int a, int b){
return len[a] + len[b] != gdis(a, b);
}
bool cent(int a, ll R){
bool found = false;
av.clear();
tng.clear();
mesl.clear();
for(int i = 0; i < n; i++)
found |= (gdis(a, i) - len[i] == R);
//cout << a << ' ' << b << ' ' << R << ' ' << found << endl;
if(!found)
return false;
int num0 = 0, num1 = 0;
for(int i = 0; i < n; i++){
if(gdis(i, a) - len[i] < R)
num0++;
if(gdis(i, a) - len[i] > R)
num1++;
if(gdis(i, a) - len[i] == R)
av.pb(i);
}
//cout << num0 << ' ' << num1 << ' ' << av.size() << endl;
if(max(num0, num1) > n / 2)
return false;
if(av.size() <= n / 2)
return true;
for(int i = 1; i < av.size(); i += 2){
if(iden(av[i], av[i - 1]))
mesl.pb(av[i]);
else{
tng.pb(av[i]);
tng.pb(av[i - 1]);
}
}
int cnt = 0, id = -1;
for(auto x : mesl){
if(cnt == 0){
cnt = 2;
id = x;
continue;
}
if(iden(x, id))
cnt += 2;
else{
cnt -= 2;
if(cnt == -1){
cnt = 1;
id = x;
}
}
}
if(int(av.size()) & 1){
if(cnt == 0)
id = av.back();
else if(!iden(av.back(), id))
cnt--;
}
if(cnt == 0 || id == -1)
return true;
cnt = 0;
for(auto u : mesl) if(iden(u, id))
cnt += 2;
for(auto u : tng) if(iden(u, id))
cnt++;
if(int(av.size()) & 1)
if(iden(id, av.back()))
cnt++;
//cout << "haaaa " << cnt << ' ' << id << endl;
return cnt <= n / 2;
}
int hubDistance(int N, int sub){
n = N;
memset(keep, -1, sizeof keep);
int dim1 = 0, dim2 = 1;
int v = 0, u = 1;
for(int i = 2; i < n; i++) if(gdis(v, u) < gdis(v, i))
u = i;
ll tR = 0;
for(int i = 0; i < n; i++){
tR = max(tR, gdis(i, u));
len[i] = (gdis(i, u) + gdis(i, v) - gdis(u, v)) / 2;
}
ll R = tR;
for(int i = 0; i < n; i++)
R = min(R, max(gdis(i, u) - len[i], tR - (gdis(i, u) - len[i])));
if(cent(u, R))
return R;
if(cent(u, tR - R))
return R;
return -R;
}
Compilation message
towns.cpp: In function 'bool cent(int, ll)':
towns.cpp:69:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | if(av.size() <= n / 2)
| ~~~~~~~~~~^~~~~~~~
towns.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 1; i < av.size(); i += 2){
| ~~^~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:134:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
134 | return R;
| ^
towns.cpp:136:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
136 | return R;
| ^
towns.cpp:137:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
137 | return -R;
| ^~
towns.cpp:119:6: warning: unused variable 'dim1' [-Wunused-variable]
119 | int dim1 = 0, dim2 = 1;
| ^~~~
towns.cpp:119:16: warning: unused variable 'dim2' [-Wunused-variable]
119 | int dim1 = 0, dim2 = 1;
| ^~~~
towns.cpp:116:28: warning: unused parameter 'sub' [-Wunused-parameter]
116 | int hubDistance(int N, int sub){
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
596 KB |
Output is correct |
| 2 |
Correct |
9 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
12 ms |
672 KB |
Output is correct |
| 5 |
Correct |
14 ms |
668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
672 KB |
Output is correct |
| 2 |
Correct |
13 ms |
724 KB |
Output is correct |
| 3 |
Correct |
14 ms |
672 KB |
Output is correct |
| 4 |
Correct |
12 ms |
668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
672 KB |
Output is correct |
| 2 |
Correct |
12 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
596 KB |
Output is correct |
| 2 |
Correct |
12 ms |
596 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
596 KB |
Output is correct |
| 2 |
Correct |
12 ms |
672 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1108 KB |
Output is correct |
