Submission #420913

#TimeUsernameProblemLanguageResultExecution timeMemory
420913maximath_1Izvanzemaljci (COI21_izvanzemaljci)C++11
5 / 100
32 ms5116 KiB
#include <iostream> #include <unordered_map> #include <algorithm> #include <set> #include <string> #include <vector> #include <random> #include <assert.h> using namespace std; mt19937 rng(420691273); #define ll long long const int MX = 5e3 + 5; const ll inf = 1e18 + 69; int n, k; vector<pair<ll, ll> > v, owo[3]; pair<pair<ll, ll>, ll> get_square(vector<pair<ll, ll> > pt){ ll mxx = pt[0].first, mnx = pt[0].first; ll mxy = pt[0].second, mny = pt[0].second; for(int i = 1; i < pt.size(); i ++){ mxx = max(mxx, pt[i].first); mnx = min(mnx, pt[i].first); mxy = max(mxy, pt[i].second); mny = min(mny, pt[i].second); } ll sz = max(1ll, max(mxx - mnx, mxy - mny)); // check validity bool ok = 1; for(int i = 0; i < pt.size(); i ++){ if(pt[i].first < mnx || pt[i].first > mnx + sz || pt[i].second < mny || pt[i].second > mny + sz) ok = 0; } if(ok) return {{mnx, mny}, sz}; else return {{-1, -1}, -1}; } int main(){ cin.tie(0) -> sync_with_stdio(0); cin >> n >> k; v.resize(n); for(int i = 0; i < n; i ++) cin >> v[i].first >> v[i].second; int all = 1; for(int i = 0; i < n; i ++) all *= k; ll mx = inf; vector<pair<pair<ll, ll>, ll> > ans; for(int msk = 0; msk < all; msk ++){ for(int i = 0; i < k; i ++) owo[i].clear(); for(int tmp = msk, i = 0; i < n; i ++, tmp /= k) owo[tmp % k].push_back(v[i]); vector<pair<pair<ll, ll>, ll> > get(k); bool valid = 1; ll mx_nw = 0ll; for(int i = 0; i < k; i ++){ if(owo[i].empty()){ valid = 0; break; } get[i] = get_square(owo[i]); if(get[i].second == -1) valid = 0; mx_nw = max(mx_nw, get[i].second); } if(valid && mx > mx_nw){ mx = mx_nw; ans = get; } } assert(mx != inf); for(auto i : ans) cout << i.first.first << " " << i.first.second << " " << i.second << endl; return 0; }

Compilation message (stderr)

izvanzemaljci.cpp: In function 'std::pair<std::pair<long long int, long long int>, long long int> get_square(std::vector<std::pair<long long int, long long int> >)':
izvanzemaljci.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 1; i < pt.size(); i ++){
      |                 ~~^~~~~~~~~~~
izvanzemaljci.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i = 0; i < pt.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...