Submission #958616

#	Time	Username	Problem	Language	Result	Execution time	Memory
958616		kilkuwu	Rail (IOI14_rail)	C++17	100 / 100	56 ms	856 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

void findLocation(int N, int F, int pos[], int type[]) {
  std::vector<int> d0(N);
  d0[0] = 0;
  pos[0] = F;
  type[0] = 1;
  std::vector<int> ord(N - 1);
  for (int i = 1; i < N; i++) {
    d0[i] = getDistance(0, i);
    ord[i - 1] = i;
  }

  std::sort(ord.begin(), ord.end(), [&](int i, int j) {
    return d0[i] < d0[j];
  });

  int S = ord[0];
  type[S] = 2;
  pos[S] = pos[0] + d0[S];

  std::vector<int> dS(N);
  dS[0] = d0[S];

  std::vector<int> left, right;
  for (int i = 1; i < N; i++) {
    if (i == S) continue;
    int ds = getDistance(S, i);
    dS[i] = ds;

    if (d0[i] == d0[S] + ds) {
      int located = pos[S] - ds;
      if (located > pos[0]) {
        pos[i] = located;
        type[i] = 1;
      } else {
        left.push_back(i);
      }
    } else {
      right.push_back(i);
    }
  }

  if (left.size()) {
    std::sort(left.begin(), left.end(), [&](int i, int j) {
      return dS[i] < dS[j];
    });

    std::vector<int> open;
    int lo = left.front();
    left.erase(left.begin());
    open.push_back(lo);
    type[lo] = 1;
    pos[lo] = pos[S] - dS[lo];
    for (int i : left) {
      int dnow = getDistance(lo, i);

      bool found = 0;
      for (int j : open) {
        // these are the open brackets 
        // we see if it works or not 
        if (dS[i] == dS[j] + dnow - (pos[j] - pos[lo])) {
          found = true;
          type[i] = 2;
          pos[i] = pos[lo] + dnow;
          break;
        }
      }

      if (!found) {
        lo = i;
        type[i] = 1;
        pos[i] = pos[S] - dS[i];
        open.push_back(i);
      }
    }
  }

  if (right.size()) {
    std::sort(right.begin(), right.end(), [&](int i, int j) {
      return d0[i] < d0[j];
    });

    dbg(right);

    std::vector<int> open;
    int lo = right.front();
    right.erase(right.begin());
    open.push_back(lo);
    type[lo] = 2;
    pos[lo] = pos[0] + d0[lo];
    dbg(lo, type[lo], pos[lo]);
    for (int i : right) {
      int dnow = getDistance(lo, i);
      dbg(i, dnow);

      bool found = 0;
      for (int j : open) {
        dbg(pos[lo] - pos[j]);
        if (d0[i] == d0[j] + dnow - (pos[lo] - pos[j])) {
          found = true;
          type[i] = 1;
          pos[i] = pos[lo] - dnow;
          break;
        }
      }

      if (!found) {
        lo = i;
        type[i] = 2;
        pos[i] = pos[0] + d0[i];
        open.push_back(i);
      }
    }
  }
}

/*
 
4
10
1 3
2 4
1 1
2 2
1 5
2 6
1 7
1 8 
1 9 
2 10



 */

#ifdef LOCAL

/* This is sample grader for the contestant */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.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;
}


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 (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;
}
#endif
//

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44