제출 #565127

#제출 시각아이디문제언어결과실행 시간메모리
565127hoanghq2004철로 (IOI14_rail)C++14
30 / 100
180 ms99148 KiB
/* This is sample grader for the contestant */ #include <bits/stdc++.h> using namespace std; //#define LOCAL #ifndef LOCAL #include "rail.h" #endif // LOCAL #ifdef LOCAL 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; } #endif const int N = 5010; int d[N][N]; int par[N]; int Find(int u) { return (u == par[u] ? u : par[u] = Find(par[u])); } int Union(int u, int v) { if ((u = Find(u)) == (v = Find(v))) return 0; par[v] = u; return 1; } int vis[N], mind[N]; void findLocation(int n, int first, int location[], int stype[]) { memset(d, -1, sizeof(d)); auto get = [&](int u, int v) { if (u == v) return 0; if (u > v) swap(u, v); if (d[u][v] == -1) d[u][v] = getDistance(u, v); return d[u][v]; }; int x = 0, y = 0; for (int z = 1; z < n; ++z) if (y == 0 || get(x, y) > get(x, z)) y = z; location[x] = first, location[y] = location[x] + get(x, y); stype[x] = 1, stype[y] = 2; vector <pair <int, int>> work; for (int z = 0; z < n; ++z) { if (z == x || z == y) continue; if (get(x, y) > get(z, y) && get(x, z) == get(y, z) + get(x, y)) { location[z] = location[y] - get(y, z); stype[z] = 1; } else work.push_back({get(x, z), z}); } set <pair <int, int>> C, D; for (int i = 0; i < n; ++i) { if (stype[i] == 1) C.insert({location[i], i}); else if (stype[i] == 2) D.insert({location[i], i}); } // cout <<x << ' ' << y << '\n'; sort(work.begin(), work.end()); for (auto [_, z]: work) { // cout << z << ' ' << get(x, z) << ' ' << get(y, z) << '\n'; if (get(x, z) > get(y, z)) { // left if (C.empty() || C.begin() -> first >= location[x]) { stype[z] = 1; location[z] = location[y] - get(y, z); } else { int t = C.begin() -> second; for (int s = 0; s < n; ++s) { if (stype[s] != 1) continue; if (get(y, z) + 2 * location[s] == location[y] + location[t] + get(t, z)) { stype[z] = 2; location[z] = get(t, z) + location[t]; break; } } if (stype[z] == 0) { stype[z] = 1; location[z] = location[y] - get(y, z); } } } else { // right if (D.empty() || (--D.end()) -> first <= location[y]) { stype[z] = 2; location[z] = location[x] + get(x, z); } else { int t = (--D.end()) -> second; for (int s = 0; s < n; ++s) { if (stype[s] != 2) continue; if (get(x, z) - 2 * location[s] == - location[x] - location[t] + get(t, z)) { stype[z] = 1; location[z] = location[t] - get(t, z); break; } } if (stype[z] == 0) { stype[z] = 2; location[z] = location[x] + get(x, z); } } } if (stype[z] == 1) C.insert({location[z], z}); else D.insert({location[z], z}); } // for (int i = 0; i < n; ++i) cout << stype[i] << ' '; // cout << '\n'; } #ifdef LOCAL 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 // LOCAL

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:124:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |     for (auto [_, z]: work) {
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...