| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 550883 | CSQ31 | Rail (IOI14_rail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* This is sample grader for the contestant */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
typedef struct Station {
int index;
int type;
int location;
int L,R;
}STATION;
long long cnt;
static int S,SUBTASK;
static STATION stations[10004];
int cmp_fun_1(const void *a,const void *b)
{
STATION c,d;
c = *(STATION*)(a);
d = *(STATION*)(b);
return c.location < d.location ? -1 : 1;
}
int cmp_fun_2(const void *a,const void *b)
{
STATION c,d;
c = *(STATION*)(a);
d = *(STATION*)(b);
return c.index < d.index ? -1 : 1;
}
void now_I_want_to_getLR(){
int now = stations[S-1].index,i;
for(i=S-2;i>=0;i--){
stations[i].R = now;
if(stations[i].type==2) now = stations[i].index;
}
now = stations[0].index;
for(i=1;i<S;i++){
stations[i].L = now;
if(stations[i].type==1) now = stations[i].index;
}
}
int getDistance(int x,int y)
{
cnt++;
if(x==y) return 0;
if(x<0 || x>=S || y<0 || y>=S) return -1;
if(stations[x].location > stations[y].location){
int tmp = x;
x = y;
y = tmp;
}
int ret = 0;
if(stations[x].type==1 && stations[y].type==1){
ret = stations[stations[y].R].location-stations[x].location+stations[stations[y].R].location-stations[y].location;
}else if(stations[x].type==1 && stations[y].type==2){
ret = stations[y].location-stations[x].location;
}else if(stations[x].type==2 && stations[y].type==2){
ret = stations[x].location-stations[stations[x].L].location+stations[y].location-stations[stations[x].L].location;
}else if(stations[x].type==2 && stations[y].type==1){
ret = stations[x].location-stations[stations[x].L].location+stations[stations[y].R].location
-stations[stations[x].L].location+stations[stations[y].R].location-stations[y].location;
}
return ret;
}
void getInput()
{
int g;
g = scanf("%d",&SUBTASK);
g = scanf("%d",&S);
int s;
for (s = 0; s < S; s++) {
int type, location;
g = scanf(" %d %d",&type,&location);
stations[s].index = s;
stations[s].location = location;
stations[s].type = type;
stations[s].L = -1;
stations[s].R = -1;
}
qsort(stations, S, sizeof(STATION), cmp_fun_1);
now_I_want_to_getLR();
qsort(stations, S, sizeof(STATION), cmp_fun_2);
}
int serverGetStationNumber()
{
return S;
}
int serverGetSubtaskNumber()
{
return SUBTASK;
}
int serverGetFirstStationLocation()
{
return stations[0].location;
}
int d[5001][5001];
int ask(int i,int j){
if(i==j)return 0;
if(d[i][j])return d[i][j];
d[i][j] = d[j][i] = getDistance(i,j);
return d[i][j];
}
void findLocation(int n, int f, int location[], int stype[])
{
location[0] = f;
stype[0] = 1;
//find the closest guy to 0
int mnn = 1e9;
int x = 0;
vector<int>l,r;
for(int i=1;i<n;i++){
if(mnn > ask(0,i)){
mnn = ask(0,i);
x = i;
}
}
stype[x] = 2;
location[x] = f + ask(0,x);
for(int i=0;i<n;i++){
if(i!=0 && i!=x){
if(ask(0,i) == ask(0,x) + ask(x,i))l.push_back(i);
else r.push_back(i);
}
}
vector<pair<int,int>>a;
for(int y:r)a.push_back({ask(0,y),y});
sort(a.begin(),a.end());
int last = x;
map<int,bool>seen;
for(auto Z : a){
int z = Z.second;
//try the path x->y->z
//will always be a upper bound to x->z
int m = ask(0,last) + ask(last,z);
m-=ask(0,z);
m/=2;
if(location[last] - m>=0 && seen[location[last] - m]){
stype[z] = 1;
location[z] = location[last] - ask(last,z);
}else{
stype[z] = 2;
location[z] = location[0] + ask(0,z);
seen[location[z]] = 1;
last = z;
}
}
a.clear();
seen.clear();
for(int y:l)a.push_back({ask(x,y),y});
sort(a.begin(),a.end());
last = 0;
for(auto Z : a){
int z = Z.second;
int m = ask(x,last) + ask(last,z);
m-=ask(x,z);
m/=2;
if(location[last] + m <= 1000000 && seen[location[last] + m]){
stype[z] = 2;
location[z] = location[last] + ask(last,z);
}else{
stype[z] = 1;
location[z] = location[x] - ask(x,z);
last = z;
seen[location[z]] = 1;
}
}
for(int i=0;i<n;i++)cout<<stype[i]<<" "<<location[i]<<'\n';
}
int main()
{
int i;
getInput();
cnt = 0;
int location[10005];
int type[10005];
int ok = 1;
findLocation(S, serverGetFirstStationLocation(),location, type);
if(SUBTASK==3 && cnt>S*(S-1)) ok = 0;
if(SUBTASK==4 && cnt>3*(S-1)) ok = 0;
for (i = 0; i < S; i++)
if(type[i]!=stations[i].type || location[i]!=stations[i].location)
ok = 0;
if(ok==0) printf("Incorrect");
else printf("Correct");
return 0;
}