| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 588633 | Tekor | 철로 (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 "grader.h"
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;
}
//#include "rail.h"
/*
*/
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define en '\n'
const int N = 5e3 + 100;
const int INTmx = (int)1e9;
int a[N],b[N],n;
bool ban[N];
int sd[N];
bool was[N][N];
int c[N][N];
int get(int x,int y) {
if(was[x][y])return c[x][y];
was[x][y] = 1;
c[x][y] = getDistance(x,y);
return c[x][y];
}
void findLocation(int NN, int first, int location[], int stype[]) {
n = NN;
location[0] = first;
stype[0] = 1;
pii mn = mp(INTmx,0);
int L = 0;
ban[0] = 1;
for(int i = 1;i < n;i++) {
if(ban[i])continue;
mn = min(mn,mp(get(L,i),i));
}
int R = mn.s;
ban[R] = 1;
location[R] = location[L] + get(L,R);
stype[R] = 2;
int kol = 2;
int lastR = location[L],lastL = location[R];
for(int i = 1;i < n;i++) {
if(ban[i])continue;
if(get(L,i) == get(R,i) + get(L,R) && get(R,i) < get(L,R)) {
stype[i] = 1;
location[i] = location[R] - get(R,i);
ban[i] = 1;
lastR = max(lastR,location[i]);
kol++;
}
}
vector <int> exR,exL;
exR.pb(R);
exL.pb(L);
//cout << R << " " << stype[R] << endl;
while(kol < n) {
mn = mp(INTmx,0);
for(int i = 1;i < n;i++) {
if(ban[i])continue;
mn = min(mn,mp(get(exL[0],i),i));
}
int pos = mn.s;
ban[pos] = 1;
//cout << pos << " ? " << get(exL[0],pos) << " === " << get(exR[0],pos) << " - " << lastR - location[exL[0]] << " + " << location[exR[0]] - lastR << en;
if(get(exL[0],pos) - (lastR - location[exL[0]]) + (location[exR[0]] - lastR) == get(exR[0],pos)) {
int val = get(R,pos);
int need = -1;
for(int i = exR.size() - 2;i >= 0;i--) {
if(val < location[R] - location[exR[i]]) {
need = i;
break;
}
}
//cout << val << " " << need << " " << pos << en;
if(need == -1) {
exR.pb(pos);
stype[pos] = 2;
location[pos] = location[exL[0]] + get(exL[0],pos);
kol++;
continue;
}
need++;
if(get(exL[0],pos) == get(exL[0],R) + val - 2 * (location[R] - location[exR[need]])) {
location[pos] = location[exR[need]] - (get(exL[0],pos) - get(exL[0],exR[need]));
stype[pos] = 1;
kol++;
}else {
exR.pb(pos);
kol++;
stype[pos] = 2;
location[pos] = location[exL[0]] + get(exL[0],pos);
}
}else {
int val = get(L,pos);
int need = -1;
for(int i = exL.size() - 2;i >= 0;i--) {
if(val < location[exL[i]] - location[L]) {
need = i;
break;
}
}
if(need == -1) {
exL.pb(pos);
stype[pos] = 1;
location[pos] = location[exR[0]] - get(exR[0],pos);
kol++;
continue;
}
need++;
if(get(exR[0],pos) == get(exR[0],L) + val - 2 * (location[exL[need]] - location[L])) {
location[pos] = location[exL[need]] + (get(exR[0],pos) - get(exR[0],exL[need]));
stype[pos] = 1;
kol++;
}else {
exL.pb(pos);
stype[pos] = 1;
location[pos] = location[exR[0]] - get(exR[0],pos);
kol++;
}
}
//cout << L << " " << R << endl;
}
}
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 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(int i = 0;i < S;i++) {
if(type[i] == 2) {
cout << i << endl;
}
}
for (i = 0; i < S; i++) {
if(type[i]!=stations[i].type || location[i]!=stations[i].location)ok = 0;
cout << location[i] << " " << type[i] << endl;
}
if(ok==0) printf("Incorrect");
else printf("Correct");
return 0;
}