Submission #420844

#TimeUsernameProblemLanguageResultExecution timeMemory
420844BertedIzvanzemaljci (COI21_izvanzemaljci)C++14
26 / 100
85 ms9788 KiB
#include <iostream> #include <cassert> #include <algorithm> #include <vector> #define int long long #define pii pair<int, int> #define ppi pair<pii, int> #define ppp pair<pii, pii> #define fst first #define snd second using namespace std; const int INF = 1e9 + 7; int N, K; vector<pii> A; pii B[100001]; ppi sqr; pii prefMin[100001], sufMin[100001]; pii prefMax[100001], sufMax[100001]; vector<ppi> ans; inline bool Intersect(const ppi &A, const ppi &B) { pii iL = {max(A.fst.fst, B.fst.fst), max(A.fst.snd, B.fst.snd)}; pii iR = {min(A.fst.fst + A.snd, B.fst.fst + B.snd), min(A.fst.snd + A.snd, B.fst.snd + B.snd)}; return (iL.fst <= iR.fst && iL.snd <= iR.snd); } inline bool comp(const pii &L, const pii &R) {return make_pair(L.snd, L.fst) < make_pair(R.snd, R.fst);} inline bool comp2(const ppi &L, const ppi &R) {return make_pair(L.snd, L.fst) > make_pair(R.snd, R.fst);} inline void solve() { if (A.size() < 2) return; for (int i = 0; i < A.size(); i++) { prefMin[i] = A[i]; prefMax[i] = A[i]; if (i) { prefMin[i].fst = min(prefMin[i - 1].fst, prefMin[i].fst); prefMin[i].snd = min(prefMin[i - 1].snd, prefMin[i].snd); prefMax[i].fst = max(prefMax[i - 1].fst, prefMax[i].fst); prefMax[i].snd = max(prefMax[i - 1].snd, prefMax[i].snd); } } for (int i = A.size() - 1; i >= 0; i--) { sufMin[i] = A[i]; sufMax[i] = A[i]; if (i + 1 < N) { sufMin[i].fst = min(sufMin[i + 1].fst, sufMin[i].fst); sufMin[i].snd = min(sufMin[i + 1].snd, sufMin[i].snd); sufMax[i].fst = max(sufMax[i + 1].fst, sufMax[i].fst); sufMax[i].snd = max(sufMax[i + 1].snd, sufMax[i].snd); } } for (int i = 0; i + 1 < A.size(); i++) { pii aL = prefMin[i], aR = prefMax[i], bL = sufMin[i + 1], bR = sufMax[i + 1]; int sA = max(aR.fst - aL.fst, aR.snd - aL.snd); int sB = max(bR.fst - bL.fst, bR.snd - bL.snd); if (sA == 0) {sA = 1;} if (sB == 0) {sB = 1;} aL.fst = aR.fst - sA; aL.snd = aR.snd - sA; if (Intersect({aL, sA}, {bL, sB})) continue; if (K == 3 && Intersect(sqr, {bL, sB})) continue; if (K == 3 && Intersect(sqr, {aL, sA})) continue; vector<ppi> temp; temp.push_back({aL, sA}); temp.push_back({bL, sB}); if (K == 3) temp.push_back(sqr); sort(temp.begin(), temp.end(), comp2); if (ans.size() && ans[0].snd <= temp[0].snd) continue; ans = temp; } } int32_t main() { ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> K; int mnY = INF, mxY = -INF, mnX = INF, mxX = -INF; for (int i = 0; i < N; i++) { cin >> B[i].fst >> B[i].snd; mnY = min(mnY, B[i].snd); mxY = max(mxY, B[i].snd); mnX = min(mnX, B[i].fst); mxX = max(mxX, B[i].fst); } ans.push_back({{mnX, mnY}, max(1LL, max(mxX - mnX, mxY - mnY))}); for (int j = 1; j < K; j++) ans.push_back({{-2000000000 - 2 * j, -2000000000 - 2 * j}, 1}); if (K == 2) { for (int i = 0; i < N; i++) A.push_back(B[i]); sort(A.begin(), A.end()); solve(); sort(A.begin(), A.end(), comp); solve(); } else if (K == 3) { } for (int i = 0; i < K; i++) { cout << ans[i].fst.fst << " " << ans[i].fst.snd << " " << ans[i].snd << "\n"; } return 0; }

Compilation message (stderr)

izvanzemaljci.cpp: In function 'void solve()':
izvanzemaljci.cpp:39:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < A.size(); i++)
      |                  ~~^~~~~~~~~~
izvanzemaljci.cpp:61:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i + 1 < A.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...
#Verdict Execution timeMemoryGrader output
Fetching results...