제출 #12201

#제출 시각아이디문제언어결과실행 시간메모리
12201qja0950철로 (IOI14_rail)C++98
30 / 100
107 ms876 KiB
#include "rail.h" #include <algorithm> #include <set> using namespace std; #define MAX_N 5005 struct FIRST{ int dis; int p; }First[MAX_N]; bool operator<(FIRST X, FIRST Y) { return X.dis < Y.dis; } set<int> C; set<int>::iterator it; void findLocation(int N, int first, int location[], int stype[]) { for(int i=1; i<N; i++) { First[i].dis = getDistance(0, i); First[i].p = i; } sort(First+1, First+N); stype[0] = 1; location[0] = first; int second = First[1].p; stype[second] = 2; location[second] = first + First[1].dis; int leftC = 0, rightD = second; C.insert(location[0]); for(int i=2; i<N; i++) { int nowp = First[i].p; int DisC = getDistance( leftC, nowp); int DisD = getDistance(rightD, nowp); int positionD = location[ leftC] + DisC; it = C.lower_bound(positionD); if(it != C.begin()) it--; int maxC = *it; // printf("%d + %d = %d\n", location[rightD] - maxC, positionD - maxC, DisD); if(location[rightD] - maxC + positionD - maxC == DisD) { stype[nowp] = 2; location[nowp] = positionD; if(positionD > location[rightD]) rightD = nowp; }else{ int positionC = location[rightD] - DisD; stype[nowp] = 1; location[nowp] = positionC; if(positionC < location[ leftC]) leftC = nowp; C.insert(positionC); } } // for(int i=0; i<N; i++) printf("[%d %d]\n", stype[i], location[i]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...