제출 #783974

#제출 시각아이디문제언어결과실행 시간메모리
783974FatihSolak철로 (IOI14_rail)C++17
56 / 100
97 ms98396 KiB
#include "rail.h" #include <bits/stdc++.h> using namespace std; int dp[5000][5000]; int tot = 0; int get(int a,int b){ if(a == b) return 0; if(dp[a][b] || dp[b][a]) return max(dp[a][b],dp[b][a]); tot--; assert(tot >= 0); return dp[a][b] = getDistance(a,b); } void findLocation(int n, int first, int location[], int stype[]){ tot = n * (n-1)/2; for(int i = 0;i<n;i++){ stype[i] = 0; for(int j = 0;j<n;j++){ dp[i][j] = 0; } } location[0] = first; stype[0] = 1; if(n == 1)return; vector<int> ord0; for(int i = 0;i<n;i++){ if(i != 0){ ord0.push_back(i); } } sort(ord0.begin(),ord0.end(),[&](int a,int b){ return get(0,a) < get(0,b); }); int posD = ord0[0]; location[posD] = location[0] + get(0,posD); stype[posD] = 2; vector<int> v; v.push_back(0); for(int i = 0;i<ord0.size();i++){ if(stype[ord0[i]])continue; if(get(0,ord0[i]) != get(posD,ord0[i]) + get(0,posD))continue; int candpos = location[v.back()] + get(v.back(),ord0[i]); int closest = -1; for(auto u:v){ if(location[u] < candpos){ if(closest == -1 || location[closest] < location[u]){ closest = u; } } } if(location[closest] >= location[0] || get(0,ord0[i]) != get(0,closest) + get(closest,ord0[i])){ v.push_back(ord0[i]); stype[ord0[i]] = 1; location[ord0[i]] = location[posD] - (get(0,ord0[i]) - get(0,posD)); } else{ stype[ord0[i]] = 2; location[ord0[i]] = candpos; } } // for(int i = 0;i<n;i++){ // if(stype[i]){ // cout << i << endl; // cout << stype[i] << ' ' << location[i] << endl; // } // } v.clear(); v.push_back(posD); for(int i = 0;i<ord0.size();i++){ if(stype[ord0[i]])continue; int candpos = location[v.back()] - get(v.back(),ord0[i]); int closest = -1; for(auto u:v){ if(location[u] > candpos){ if(closest == -1 || location[closest] > location[u]){ closest = u; } } } if(get(0,ord0[i]) != get(0,closest) + get(closest,ord0[i])){ v.push_back(ord0[i]); stype[ord0[i]] = 2; location[ord0[i]] = location[0] + get(0,ord0[i]); } else{ stype[ord0[i]] = 1; location[ord0[i]] = candpos; } } // for(int i = 0;i<n;i++){ // if(stype[i]){ // cout << i << endl; // cout << stype[i] << ' ' << location[i] << endl; // } // } }

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

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0;i<ord0.size();i++){
      |                   ~^~~~~~~~~~~~
rail.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0;i<ord0.size();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...