This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int MAXN = 5005;
const int MAXM = 1000005;
const int INF = 1000000000;
int n, x, y, lef, rig;
int pos[MAXN], tip[MAXN];
int d[MAXN][MAXN];
vector < pair <int, int> > v;
int ima[MAXM];
//int getDistance (int x, int y) {return 1;}
void nadi (int x, int y) {
if (d[x][y] != -1) return;
d[x][y] = getDistance(x, y);
}
bool dodaj1 (int k) {
pos[k] = pos[lef] + d[k][lef]; tip[k] = 2;
if (pos[rig] < pos[k]) {
int ofs = d[k][rig] - (pos[k] - pos[rig]);
if (ofs < 0 || (ofs & 1)) return 0;
int p = pos[rig] - ofs/2;
if (ima[p] && pos[0] <= p && p < pos[rig]) return 1;
} else if (pos[k] < pos[0]) {
int ofs = d[k][rig] - (pos[rig] - pos[k]);
if (ofs < 0 || (ofs & 1)) return 0;
int p = pos[k] - ofs/2;
if (ima[p] && pos[lef] <= p && p < pos[k]) return 1;
}
return 0;
}
bool dodaj2 (int k) {
pos[k] = pos[rig] - d[k][rig]; tip[k] = 1;
if (pos[k] < pos[lef]) {
int ofs = d[k][lef] - (pos[lef] - pos[k]);
if (ofs < 0 || (ofs & 1)) return 0;
int p = pos[lef] + ofs/2;
if (ima[p] && p <= pos[rig]) return 1;
} else if (pos[0] < pos[k]) {
int ofs = d[k][lef] - (pos[k] - pos[lef]);
if (ofs < 0 || (ofs & 1)) return 0;
int p = pos[k] + ofs/2;
if (ima[p] && p <= pos[rig]) return 1;
}
return 0;
}
void findLocation (int N, int X, int location[], int stype[]) {
n = N; x = X;
memset(d, -1, sizeof d);
pos[0] = x; tip[0] = 1; ima[x] = 1;
for (int j=1; j<n; j++) {
nadi(0, j);
v.push_back(make_pair(d[0][j], j));
}
sort(v.begin(), v.end());
y = v[0].second;
pos[y] = x + d[0][y]; tip[y] = 2; ima[pos[y]] = 1;
lef = 0, rig = y;
for (auto par : v) {
int k = par.second;
if (k == lef || k == rig) continue;
nadi(k, lef); nadi(k, rig);
if (!dodaj1(k)) dodaj2(k);
ima[pos[k]] = 1;
}
for (int i=0; i<n; i++) {
location[i] = pos[i];
stype[i] = tip[i];
}
}
/*int main () {
return 0;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |