제출 #1198109

#제출 시각아이디문제언어결과실행 시간메모리
1198109mychecksedadHamburg Steak (JOI20_hamburg)C++20
2 / 100
1645 ms1114112 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, k; array<int, 4> a[N]; void solve(){ cin >> n >> k; vector<array<int, 4>> p; for(int i = 1; i <= n; ++i){ cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3]; p.pb(a[i]); } vi XS, YS; for(int j = 0; j < k; ++j){ int X = 1000000001; vector<array<int, 4>> np; for(auto x: p){ X = min(X, x[2]); } for(auto x: p){ if(x[0] <= X && X <= x[2]){ // nothing to do actually }else{ np.pb(x); } } np.swap(p); XS.pb(X); } assert(p.empty()); for(int i = 1; i <= n; ++i){ p.pb(a[i]); } for(int j = 0; j < k; ++j){ int Y = 1000000001; vector<array<int, 4>> np; for(auto x: p){ Y = min(Y, x[3]); } for(auto x: p){ if(x[1] <= Y && Y <= x[3]){ // nothing to do actually }else{ np.pb(x); } } np.swap(p); YS.pb(Y); } assert(p.empty()); assert(XS.size() * YS.size() <= k*k); if(XS.size() * YS.size() <= k){ for(int x: XS){ for(int y: YS) {cout << x << ' ' << y << '\n'; k--;} } for(int i = 0; i < k; ++i) cout << 1 << ' ' << 1 << '\n'; return; } vector<array<int, 2>> P; for(int x: XS){ for(int y: YS) P.pb({x, y}); } int m = P.size(); for(int j = 0; j < (1<<m); ++j){ if(__builtin_popcount(j) != k) continue; bool ok = true; vector<array<int, 2>> v; for(int jj = 0; jj < m; ++jj){ if((1<<jj)&j) v.pb(P[jj]); } for(int i = 1; i <= n; ++i){ bool f = false; for(auto [x,y]: v){ if(a[i][0] <= x && x <= a[i][2] && a[i][1] <= y && y <= a[i][3]){ f = true; } } ok = ok & f; } if(ok){ for(auto [x, y]: v){ cout << x << ' ' << y << '\n'; } return; } } vi v; for(int i = 0; i < MOD; ++i){ v.pb(i); } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...