제출 #1088762

#제출 시각아이디문제언어결과실행 시간메모리
1088762alexz1205Aliens (IOI16_aliens)C++14
60 / 100
2040 ms16316 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long int lint; typedef __int128 llint; typedef long double ldoub; const int N = 1e5; const llint PREC = 1e4; array<llint, 2> ransDat[N]; vector<array<llint, 2>> rans; llint dp[N+1]; int dp2[N+1]; int n, m; void print(__int128 x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) print(x / 10); putchar(x % 10 + '0'); } llint slope(llint sl1p1, llint sl1p2, llint sl2p1, llint sl2p2){ llint a = sl1p1, b = sl1p2, c = sl2p1, d = sl2p2; for (int x = 0; x < 200; x ++){ llint k1 = sl1p1 / sl1p2; llint k2 = sl2p1 / sl2p2; if (k1 != k2){ llint v = a*d - b*c; assert(v != 0); bool b1 = v < 0, b2 = (k1-k2) < 0; assert(b1 == b2); return k1 - k2; } sl1p1 %= sl1p2; sl2p1 %= sl2p2; sl1p1 <<= 1; sl2p1 <<= 1; } llint v = a*d - b*c; assert(v == 0); return 0; } void calc(llint adjust){ deque<array<llint, 3>> hull; hull.push_back({rans[0][0], -rans[0][0] * rans[0][0], 0}); for (int x = 0; x < rans.size(); x ++){ llint s = -2 * rans[x][1]; llint B = rans[x][1] * rans[x][1]; int a = 1, b = hull.size()-1; while (a <= b){ int mid = (b-a+1)/2 + a; llint slp1 = (hull[mid][1] - hull[mid-1][1]); llint slp2 = (hull[mid][0] - hull[mid-1][0]); if (slope(slp1, slp2, s, (llint)1) < 0){ b = mid-1; }else { a = mid+1; } } int r = a-1; dp[x] = -hull[r][1] + B + hull[r][0] * s + adjust; dp2[x] = hull[r][2] + 1; /* print(dp[x]); cout << " "; print((dp[x] - dp2[x]*adjust)/PREC/PREC); cout << " " << dp2[x] << endl; */ if (x == rans.size()-1) continue; llint right = min(rans[x][1], rans[x+1][0]); array<llint, 3> p = {rans[x+1][0], -dp[x] + (rans[x][1] - right) * (rans[x][1] - right) - rans[x+1][0] * rans[x+1][0], dp2[x]}; while (hull.size() > 1){ llint sl1p1 = (p[1] - hull[hull.size()-2][1]); llint sl1p2 = (p[0] - hull[hull.size()-2][0]); llint sl2p1 = (hull[hull.size()-1][1] - hull[hull.size()-2][1]); llint sl2p2 = (hull[hull.size()-1][0] - hull[hull.size()-2][0]); if (slope(sl1p1, sl1p2, sl2p1, sl2p2) >= 0){ hull.pop_back(); }else { break; } } hull.push_back(p); } } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { // dp_i = (pos_i-pos_j)**2 - (pos_right_j - pos_j)**2 + dp_j // (pos_right_j - pos_j) ** 2 - dp_j - pos_j ** 2 = pos_i ** 2 - dp_i - 2 * pos_i * pos_j // dp_i = (pos_i - pos_j + pos_right_j - pos_j) * (pos_i - pos_right_j) + dp_j // dp_i = pos_i ** 2 - 2 * pos_j * pos_i + 2 * pos_j * pos_right_j - pos_right_j ** 2 + dp_j // (pos_right_j ** 2 - 2 * pos_j * pos_right_j - dp_j) = pos_i ** 2 - dp_i + (- 2 * pos_j * pos_i) // // subsume all within range // transition from possible left endpoints ::n = n; ::m = m; for (int x = 0; x < n; x ++){ ransDat[x][0] = PREC*min(r[x], c[x]); ransDat[x][1] = PREC*(max(r[x], c[x]) + 1); } sort(ransDat, ransDat+n, [](array<llint, 2> a, array<llint, 2> b){return (a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]);}); { llint ma = 0; for (int x = 0; x < n; x ++){ if (ma >= ransDat[x][1]){ continue; } ma = ransDat[x][1]; rans.push_back(ransDat[x]); } } k = min(k, (int)rans.size()); llint a = -(llint)1e12 * PREC * PREC, b = (llint)1e12 * PREC * PREC; pair<llint, int> up = {1e12 * PREC*PREC, -1}; pair<llint, int> low = {1e12 * PREC*PREC, -1}; while (a <= b){ llint mid = (b-a+1)/2 + a; llint v = mid; calc(v); /* print(mid); cout << " "; print(dp[rans.size()-1]); llint val = dp[rans.size()-1]; val -= dp2[rans.size()-1]*v; val /= PREC; val /= PREC; cout << " "; print(val); cout << " " << dp2[rans.size()-1] << endl;; */ if (dp2[rans.size()-1] == k){ llint val = dp[rans.size()-1]; val -= k*v; val /= PREC; val /= PREC; return (lint)val; } if (dp2[rans.size()-1] < k){ llint val = dp[rans.size()-1]; val -= dp2[rans.size()-1]*v; val /= PREC; val /= PREC; up = {val, dp2[rans.size()-1]}; b = mid-1; }else { llint val = dp[rans.size()-1]; val -= dp2[rans.size()-1]*v; val /= PREC; val /= PREC; low = {val, dp2[rans.size()-1]}; a = mid+1; } } llint best = ((up.first-low.first) * (k-low.second))/(up.second - low.second) + low.first; return best; //return low.second; //return up.second * 1e12 + low.second*1e6 + k; //exit(-1); //return 0; }

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

aliens.cpp: In function 'void calc(llint)':
aliens.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<__int128, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for (int x = 0; x < rans.size(); x ++){
      |                  ~~^~~~~~~~~~~~~
aliens.cpp:80:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<__int128, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   if (x == rans.size()-1) continue;
      |       ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...