| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 283413 |
2020-08-25T16:42:17 Z |
rqi |
Rail (IOI14_rail) |
C++14 |
|
95 ms |
636 KB |
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define mp make_pair
#define f first
#define s second
#define bk back()
#define pb push_back
#define all(x) begin(x), end(x)
#define ins insert
const int MOD = 1000000007;
const int mx = 5005;
int pos1[mx];
int pos2[mx];
void findLocation(int N, int first, int location[], int stype[])
{
// cout << "B1\n";
// cout.flush();
stype[0] = 1;
location[0] = 0;
pi mn = mp(MOD, -1);
for(int i = 1; i < N; i++){
pos1[i] = getDistance(0, i);
mn = min(mn, mp(pos1[i], i));
}
stype[mn.s] = 2;
location[mn.s] = mn.f;
pi c = mp(mn.f, 0); //distance from mn.s
for(int i = 1; i < N; i++){
if(i == mn.s) continue;
pos2[i] = getDistance(mn.s, i);
c = min(c, mp(pos2[i], i));
}
c.f = mn.f-c.f; //position
//cout << mn.f << " " << mn.s << " " << c.f << " " << c.s << "\n";
// cout << "B2\n";
// cout.flush();
stype[c.s] = 1;
location[c.s] = c.f;
vpi lefs; //distance from a1, index
vpi rigs; //distance from 0, index
for(int i = 1; i < N; i++){
if(i == mn.s || i == c.s) continue;
int diff = pos1[i]-pos2[i];
if(diff == mn.f){ //left of a1
lefs.pb(mp(pos2[i], i));
}
else{ //right of a1
rigs.pb(mp(pos1[i], i));
}
}
sort(all(lefs));
sort(all(rigs));
// cout << "B3\n";
// cout.flush();
// cout << "lefs: \n";
// for(auto u: lefs){
// cout << u.f << " " << u.s << "\n";
// }
// cout << "rigs: \n";
// for(auto u: rigs){
// cout << u.f << " " << u.s << "\n";
// }
// cout << "\n";
{
pi cur; //distance, index of C
cur = mp(mn.f, 0);
set<int> t;
t.ins(cur.f);
for(auto u: lefs){
if(u.f < mn.f){
stype[u.s] = 1;
location[u.s] = mn.f-u.f;
continue;
}
int d = getDistance(cur.s, u.s);
int diff = u.f-d;
bool case2 = 0;
if((diff+cur.f) % 2 == 0 && t.count((diff+cur.f)/2)) case2 = 1;
// for(auto x: cur){
// if(diff == x.f-(cur.bk.f-x.f)) case2 = 1;
// }
if(case2){
stype[u.s] = 2;
location[u.s] = mn.f-cur.f+d;
}
else{
stype[u.s] = 1;
location[u.s] = mn.f-u.f;
cur = u;
t.ins(cur.f);
}
// if(u.f != cur.f+d){
// stype[u.s] = 1;
// location[u.s] = mn.f-u.f;
// cur = u;
// }
// else{
// stype[u.s] = 2;
// location[u.s] = mn.f-cur.f+d;
// }
}
}
{
pi cur;
cur = mp(mn.f, mn.s);
set<int> t;
t.ins(mn.f);
for(auto u: rigs){
int d = getDistance(cur.s, u.s);
int diff = u.f-d;
bool case2 = 0;
if((diff+cur.f) % 2 == 0 && t.count((diff+cur.f)/2)) case2 = 1;
// for(auto x: cur){
// if(diff == x.f-(cur.bk.f-x.f)) case2 = 1;
// }
if(case2){
stype[u.s] = 1;
location[u.s] = cur.f-d;
}
else{
stype[u.s] = 2;
location[u.s] = u.f;
cur = u;
t.ins(cur.f);
}
// if(u.f != cur.f+d){
// cout << u.f << " " << u.s << "\n";
// stype[u.s] = 2;
// location[u.s] = u.f;
// cur = u;
// }
// else{
// stype[u.s] = 1;
// location[u.s] = cur.f-d;
// }
}
}
for(int i = 0; i < N; i++){
location[i]+=first;
//cout << stype[i] << " " << location[i] << "\n";
}
// cout << "B5\n";
// cout.flush();
// stype[0] = 1;
// location[0] = first;
// pi mn = mp(MOD, -1);
// for(int i = 1; i < N; i++){
// pos1[i] = getDistance(0, i);
// mn = min(mn, mp(pos1[i], i));
// }
// stype[mn.s] = 2;
// location[mn.s] = first+mn.f;
// for(int i = 1; i < N; i++){
// if(i == mn.s) continue;
// pos2[i] = getDistance(mn.s, i);
// }
// for(int i = 1; i < N; i++){
// if(i == mn.s) continue;
// if(pos1[i] > pos2[i]){
// stype[i] = 1;
// location[i] = first-(pos1[i]-2*mn.f);
// }
// else{
// stype[i] = 2;
// location[i] = first+pos1[i];
// }
// }
// stype[0] = 1;
// location[0] = first;
// for(int i = 1; i < N; i++){
// stype[i] = 2;
// location[i] = location[0]+getDistance(0, i);
// }
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
416 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
596 KB |
Output is correct |
| 2 |
Correct |
87 ms |
632 KB |
Output is correct |
| 3 |
Correct |
87 ms |
632 KB |
Output is correct |
| 4 |
Correct |
87 ms |
596 KB |
Output is correct |
| 5 |
Correct |
91 ms |
632 KB |
Output is correct |
| 6 |
Correct |
89 ms |
596 KB |
Output is correct |
| 7 |
Correct |
88 ms |
632 KB |
Output is correct |
| 8 |
Correct |
86 ms |
604 KB |
Output is correct |
| 9 |
Correct |
87 ms |
632 KB |
Output is correct |
| 10 |
Correct |
87 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
632 KB |
Output is correct |
| 2 |
Correct |
87 ms |
632 KB |
Output is correct |
| 3 |
Correct |
86 ms |
632 KB |
Output is correct |
| 4 |
Correct |
95 ms |
636 KB |
Output is correct |
| 5 |
Correct |
88 ms |
632 KB |
Output is correct |
| 6 |
Correct |
85 ms |
632 KB |
Output is correct |
| 7 |
Correct |
88 ms |
600 KB |
Output is correct |
| 8 |
Correct |
89 ms |
632 KB |
Output is correct |
| 9 |
Correct |
87 ms |
632 KB |
Output is correct |
| 10 |
Correct |
86 ms |
632 KB |
Output is correct |
| 11 |
Correct |
87 ms |
632 KB |
Output is correct |
| 12 |
Correct |
86 ms |
632 KB |
Output is correct |
| 13 |
Correct |
85 ms |
592 KB |
Output is correct |
| 14 |
Correct |
85 ms |
600 KB |
Output is correct |
| 15 |
Correct |
90 ms |
632 KB |
Output is correct |
| 16 |
Correct |
88 ms |
632 KB |
Output is correct |
| 17 |
Correct |
88 ms |
636 KB |
Output is correct |
| 18 |
Correct |
85 ms |
632 KB |
Output is correct |
| 19 |
Correct |
89 ms |
632 KB |
Output is correct |
| 20 |
Correct |
89 ms |
632 KB |
Output is correct |
