제출 #1063329

#제출 시각아이디문제언어결과실행 시간메모리
1063329andrei_iorgulescu철로 (IOI14_rail)C++14
100 / 100
56 ms740 KiB
#include <bits/stdc++.h> #include "rail.h" #warning That's not FB, that's my FB /** on a personal note, nu am nici cel mai mic proof matematic pentru de ce ar merge :) tehnic, asta era primul "4n cu bulaneala" **/ using namespace std; int d0[5005]; int d1[5005]; int d; bool cmp(int x, int y) { return d0[x] < d0[y]; } void findLocation(int n, int first, int location[], int stype[]) { stype[0] = 1; location[0] = first; for (int i = 1; i < n; i++) d0[i] = getDistance(0,i); int f, kmin = 1e9; for (int i = 1; i < n; i++) { if (d0[i] < kmin) f = i, kmin = d0[i]; } d = kmin; stype[f] = 2; location[f] = location[0] + kmin; for (int i = 1; i < n; i++) if (i != f) d1[i] = getDistance(f,i); vector<int> st,dr; for (int i = 1; i < n; i++) { if (i != f) { if (d0[i] < 2 * d and d1[i] < d and d0[i] - d1[i] == d) { stype[i] = 1; location[i] = location[f] - d1[i]; } else if (d1[i] == d0[i] - d) st.push_back(i); else dr.push_back(i); } } sort(st.begin(), st.end(), cmp); sort(dr.begin(), dr.end(), cmp); vector<int> jos; for (auto it : st) { vector<int> candi, loci; for (int i = 0; i < jos.size(); i++) { int upb; if (i == 0) upb = location[0] - location[jos[i]]; else upb = location[jos[i - 1]] - location[jos[i]]; upb--; int dsmin = d1[jos[i]] + 1, dsmax = dsmin + upb - 1; if (d1[it] >= dsmin and d1[it] <= dsmax) candi.push_back(i), loci.push_back(location[jos[i]] + (d1[it] - d1[jos[i]])); } if (candi.empty()) { stype[it] = 1; location[it] = location[f] - d1[it]; jos.push_back(it); } else { int js = jos.back(); int qr = getDistance(it, js); int p2 = location[js] + qr; bool yeah = false; for (auto itt : loci) { if (itt == p2) { stype[it] = 2; location[it] = p2; yeah = true; } } if (!yeah) { jos.push_back(it); stype[it] = 1; location[it] = location[f] - d1[it]; } } } vector<int> sus; for (auto it : dr) { vector<int> candi, loci; for (int i = 0; i < sus.size(); i++) { int upb; if (i == 0) upb = location[sus[i]] - location[f]; else upb = location[sus[i]] - location[sus[i - 1]]; upb--; int dsmin = d1[sus[i]] + 1, dsmax = dsmin + upb - 1; if (d1[it] >= dsmin and d1[it] <= dsmax) candi.push_back(i), loci.push_back(location[sus[i]] - (d1[it] - d1[sus[i]])); } if (candi.empty()) { stype[it] = 2; location[it] = d0[it] + location[0]; sus.push_back(it); } else { int ss = sus.back(); int qr = getDistance(it, ss); int p2 = location[ss] - qr; bool yeah = false; for (auto itt : loci) { if (itt == p2) { stype[it] = 1; location[it] = p2; yeah = true; } } if (!yeah) { sus.push_back(it); stype[it] = 2; location[it] = location[0] + d0[it]; } } } //for (int i = 0; i < n; i++) // cout << stype[i] << ' ' << location[i] << endl; } /** d(i,j) = d(j,i) ofc Iau toate d(0,i) -> d(i); gasesc aia minima, o sa fie prima D in dreapta, fie ea p, si fie d = d(p) Iau toate d(p,i) -> d2(i); pentru fiecare i != 0 si i != p, e usor de aflat din astea daca e cumva intre 0 si p (si chiar pozitia lui), tipul fiind C In plus, pentru alea aflate in stanga lui 0, d2(i) o sa fie d1(i) - d, iar daca o sa fie in dreapta, d2(i) o sa fie strict mai mare ca d1(i) - d Acum, departajand in stanga, fac o chestie dubioasa de le iau crescator, am doua variante (ori un C nou in stanga de tot, ori un D pe undeva stabilit) Intre alea doua variante stabilesc cu inca un query de distanta Cred ca ceva de genul ar trebui sa iasa si in dreapta si raman in N - 1 + N - 2 + N - 2 = maxim 3N - 5 query-uri Sunt bot but it can be fixed **/

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

rail.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i = 0; i < jos.size(); i++)
      |                         ~~^~~~~~~~~~~~
rail.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for (int i = 0; i < sus.size(); i++)
      |                         ~~^~~~~~~~~~~~
rail.cpp:34:11: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |     stype[f] = 2;
      |           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...