Submission #757976

#TimeUsernameProblemLanguageResultExecution timeMemory
757976ProtonDecay314Towers (NOI22_towers)C++17
16 / 100
539 ms16884 KiB
/* Time complexity: O(N^2 2^N) general case (which should pass 1-2) Subtask 3 This is a rectangle (wow) So what it looks like is this: T---T -T-T- --T-- ----- --T-- -T-T- T---T We just have to construct this, essentially Subtask 4 For this one, we go through every x-coordinate and get the smallest Y and largest Y Well, we can probably sort the values by Y and then I can keep a set of encountered Xs // ! Warning: the set may increase the constant factor if an X has been encountered, then don't bother with it anymore Now do the same, but going in reverse order of Y */ #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<bool> solve16(ll n, const vector<tuple<ll, ll>>& pos) { vector<ll> xs; vector<ll> ys; for(const tuple<ll, ll>& tup : pos) { ll x, y; tie(x, y) = tup; xs.push_back(x); ys.push_back(y); } for(ll i = 0; i < (1 << n); i++) { vector<bool> third_satisfied(n, false); ll has_bad_x_coords = false; for(ll targx : xs) { /* TODO count the number of towers with this x mark the ones in the middle as "satisfied" */ ll count_towers = 0ll; ll min_tower_y = numeric_limits<ll>::max(); ll max_tower_y = numeric_limits<ll>::min(); for(ll j = 0ll; j < n; j++) { ll x, y; tie(x, y) = pos[j]; if(x == targx) { if((i >> j) & 1) { count_towers++; third_satisfied[j] = true; min_tower_y = min(min_tower_y, y); max_tower_y = max(max_tower_y, y); } } } if(count_towers > 2ll) { has_bad_x_coords = true; break; } for(ll j = 0ll; j < n; j++) { ll x, y; tie(x, y) = pos[j]; if(x == targx) { if(min_tower_y <= y && y <= max_tower_y) { third_satisfied[j] = true; } } } } if(has_bad_x_coords) continue; ll has_bad_y_coords = false; for(ll targy : ys) { /* TODO count the number of towers with this y mark the ones in the middle as "satisfied" */ ll count_towers = 0ll; ll min_tower_x = numeric_limits<ll>::max(); ll max_tower_x = numeric_limits<ll>::min(); for(ll j = 0ll; j < n; j++) { ll x, y; tie(x, y) = pos[j]; if(y == targy) { if((i >> j) & 1) { count_towers++; third_satisfied[j] = true; min_tower_x = min(min_tower_x, x); max_tower_x = max(max_tower_x, x); } } } if(count_towers > 2ll) { has_bad_y_coords = true; break; } for(ll j = 0ll; j < n; j++) { ll x, y; tie(x, y) = pos[j]; if(y == targy) { if(min_tower_x <= x && x <= max_tower_x) { third_satisfied[j] = true; } } } } if(has_bad_y_coords) continue; if(all_of(third_satisfied.begin(), third_satisfied.end(), [](bool v) {return v;})) { vector<bool> ans; for(ll j = 0ll; j < n; j++) { ans.push_back((i >> j) & 1); } return ans; } } } int main() { ll n; cin >> n; vector<tuple<ll, ll>> pos; for(ll i = 0ll; i < n; i++) { ll x, y; cin >> x >> y; pos.push_back({x, y}); } if(n <= 16) { vector<bool> ans = solve16(n, pos); for(bool v : ans) { cout << v; } cout << endl; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'std::vector<bool> solve16(ll, const std::vector<std::tuple<long long int, long long int> >&)':
Main.cpp:33:16: warning: control reaches end of non-void function [-Wreturn-type]
   33 |     vector<ll> xs;
      |                ^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...