Submission #139152

#	Time	Username	Problem	Language	Result	Execution time	Memory
139152		evpipis	철로 (IOI14_rail)	C++11	30 / 100	117 ms	1432 KiB

rail

//#define TEST

#ifndef TEST
#include "rail.h"
#endif // TEST

#include <bits/stdc++.h>
using namespace std;

#ifdef TEST
void findLocation(int n, int first, int loc[], int stype[]);

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()
{
    //freopen("sample-2-1.in", "r", stdin);
  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 // TEST


#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 5005;
map<ii, int> mym;
int st1, st2;
vector<int> vec;

//int hello_cnt = 0;

int dis(int a, int b){
    if (a == b) return 0;
    if (a > b) swap(a, b);
    if (mym.count(mp(a, b))) return mym[mp(a, b)];

    //hello_cnt++;
    //printf("asked: a = %d, b = %d\n", a, b);
    return mym[mp(a, b)] = getDistance(a, b);
}

bool comp1(int a, int b){
    return (dis(st1, a) < dis(st1, b));
}

bool comp2(int a, int b){
    return (dis(st2, a) < dis(st2, b));
}

void findLocation(int n, int first, int loc[], int stype[]){
    loc[0] = first;
    stype[0] = 1;

    if (n == 1)
        return;

    st1 = 0, st2 = -1;
    for (int i = 1; i < n; i++)
        if (st2 == -1 || dis(st1, i) < dis(st1, st2))
            st2 = i;

    vec.pb(st2);
    for (int i = 0; i < n; i++)
        if (i != st1 && dis(st1, i) < dis(st2, i))
            vec.pb(i);
    sort(vec.begin(), vec.end(), comp1);

    int last = -1;
    for (int i = 0; i < vec.size(); i++){
        int nex = vec[i];
        if (last == -1 || dis(st1, nex) < dis(last, nex)){
            loc[nex] = loc[st1]+dis(st1, nex);
            stype[nex] = 2;
            last = nex;
        }
        else{
            loc[nex] = loc[last]-dis(last, nex);
            stype[nex] = 1;
        }
    }

    vec.clear();
    vec.pb(st1);
    for (int i = 0; i < n; i++)
        if (i != st2 && dis(st2, i) < dis(st1, i))
            vec.pb(i);
    sort(vec.begin(), vec.end(), comp2);

    last = -1;
    for (int i = 0; i < vec.size(); i++){
        int nex = vec[i];
        if (last == -1 || dis(st2, nex) < dis(last, nex)){
            loc[nex] = loc[st2]-dis(st2, nex);
            stype[nex] = 1;
            last = nex;
        }
        else{
            loc[nex] = loc[last]+dis(last, nex);
            stype[nex] = 2;
        }
    }

    //printf("used: %d\n", hello_cnt);
    //for (int i = 0; i < n; i++)
      //  printf("i = %d, tp = %d, loc = %d\n", i, stype[i], loc[i]);
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:185:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~
rail.cpp:206:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~

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