fork download
copy 
  1. /*
  2.     The Fool that doesn't belong to this era;
  3.     The Mysterious Ruler above the Gray Fog;
  4.     The King of Yellow and Black who wields good luck
  5. */
  6. #include <bits/stdc++.h>
  7. #define ll long long
  8. #define ft first
  9. #define sc second
  10. #define el '\n'
  11. #define FOR(i,a,b) for (ll i = (a), _b = (b); i <= _b; i ++)
  12. #define FORD(i,b,a) for (ll i = (b), _a = (a); i >= _a; i --)
  13. #define boost ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  14. #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout)
  15. #define pb push_back
  16. #define all(x) (x).begin(),(x).end()
  17. using namespace std;
  18. #define MASK(i) (1LL << (i))
  19. #define BIT(x, i) (((x) >> (i)) & 1LL)
  20.  
  21. const ll N = 2e5;
  22. ll n;
  23.  
  24. struct A {
  25.     ll x, y, z, t;
  26. };
  27.  
  28. vector<A> a;
  29.  
  30. namespace Sub1 {
  31.     bool check() {
  32.         if(n > 200) return 0;
  33.         for(auto [x, y, z, t] : a) if(x > 200 || y > 200 || z > 200 || t > 200) return 0;
  34.         return 1;
  35.     }
  36.  
  37.     void solve() {
  38.         pair<ll, ll> ansPair = {1e18, 1e18};
  39.  
  40.         FOR(i, 0, 200) FOR(j, 0, 200) {
  41.             ll cnt = 0;
  42.             for(auto [x, y, z, t] : a) {
  43.                 if(x <= i && i <= y && z <= j && j <= t) cnt ++;
  44.             }
  45.  
  46.             if(cnt >= n) {
  47.                 ansPair = min(ansPair, {i, j});          
  48.             }
  49.  
  50.         }
  51.  
  52.         if(ansPair.ft == 1e18 || ansPair.sc == 1e18) cout << -1;
  53.         else cout << ansPair.ft << ' ' << ansPair.sc;
  54.     }
  55. }
  56.  
  57. namespace Sub2 {
  58.     bool check() {
  59.         return (n <= 2000);
  60.     }
  61.  
  62.     A giao(A pos1, A pos2) {
  63.         return {max(pos1.x, pos2.x), min(pos1.y, pos2.y), max(pos1.z, pos2.z), min(pos1.t, pos2.t)};
  64.     }
  65.  
  66.     void solve() {
  67.         pair<ll, ll> ans = {1e18, 1e18};
  68.  
  69.         FOR(i, 0, n) {
  70.             ll cnt = 0;
  71.             A pre = {0, 0, 0, 0};
  72.  
  73.             FOR(j, 0, n) if(i != j) {
  74.                 cnt ++;
  75.                 if(cnt == 1) pre = a[j];
  76.                 else pre = giao(pre, a[j]);
  77.                 if(pre.x > pre.y || pre.z > pre.t) break;
  78.             }
  79.  
  80.             if(cnt >= n) {
  81.                 if(ans.ft + ans.sc > pre.x + pre.z) ans = {pre.x, pre.z};
  82.                 else if(ans.ft + ans.sc == pre.x + pre.z) ans = min(ans, {pre.x, pre.z});
  83.             }
  84.         }
  85.  
  86.         if(ans.ft == 1e18 || ans.sc == 1e18) cout << -1;
  87.         else cout << ans.ft << ' ' << ans.sc;
  88.     }
  89. }
  90.  
  91. namespace Sub3 {
  92.     A prefix[N + 1], suffix[N + 1];
  93.  
  94.     bool check() {
  95.         return 1;
  96.     }
  97.  
  98.     A giao(A pos1, A pos2) {
  99.         return {max(pos1.x, pos2.x), min(pos1.y, pos2.y), max(pos1.z, pos2.z), min(pos1.t, pos2.t)};
  100.     }
  101.  
  102.     bool check(A pre) {
  103.         if(pre.x > pre.y || pre.z > pre.t) return 0;
  104.         return 1;
  105.     }
  106.  
  107.     void solve() {
  108.         prefix[0] = a[0]; suffix[n] = a[n];
  109.         FOR(i, 1, n)  prefix[i] = giao(prefix[i - 1], a[i]);
  110.         FORD(i, n - 1, 0) suffix[i] = giao(suffix[i + 1], a[i]);
  111.  
  112.         pair<ll, ll> ans = {1e18, 1e18};
  113.         if(check(prefix[n - 1])) ans = {prefix[n - 1].x, prefix[n - 1].z};
  114.         if(check(suffix[1])) {
  115.             if(ans.ft == 1e18) ans = {suffix[1].x, suffix[1].z};
  116.             else {
  117.                 if(ans.ft + ans.sc > suffix[1].x + suffix[1].z) ans = {suffix[1].x, suffix[1].z};
  118.                 else if(ans.ft + ans.sc == suffix[1].x + suffix[1].z) ans = min(ans, {suffix[1].x, suffix[1].z});
  119.             }
  120.         }
  121.  
  122.         FOR(i, 1, n - 1) {
  123.             A pre = giao(prefix[i - 1], suffix[i + 1]);
  124.             if(check(pre)) {
  125.                 if(ans.ft + ans.sc > pre.x + pre.z) ans = {pre.x, pre.z};
  126.                 else if(ans.ft + ans.sc == pre.x + pre.z) ans = min(ans, {pre.x, pre.z});
  127.             }
  128.         }
  129.  
  130.         if(ans.ft == 1e18 || ans.sc == 1e18) cout << -1;
  131.         else cout << ans.ft << ' ' << ans.sc;
  132.     }
  133. }
  134.  
  135. void read() {
  136.     cin >> n;
  137.     FOR(i, 1, n + 1) {
  138.         ll x, y, z, t; cin >> x >> y >> z >> t;
  139.         a.pb({x, z, t, y});
  140.     }
  141. }
  142.  
  143. void solve() {
  144.     if(Sub1::check()) {Sub1::solve(); return;}
  145.     if(Sub2::check()) {Sub2::solve(); return;}
  146.     if(Sub3::check()) {Sub3::solve(); return;}
  147. }
  148.  
  149. void write() {
  150.  
  151. }
  152.  
  153. int main() {
  154.     boost;
  155.     //file();
  156.     read();
  157.     solve();
  158.     write();
  159.     return 0;
  160. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/H4zBY4
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!