제출 #1213215

#제출 시각아이디문제언어결과실행 시간메모리
1213215emptypringlescanHamburg Steak (JOI20_hamburg)C++17
15 / 100
3093 ms43512 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("bmi,bmi2,avx2,popcnt,lzcnt") int n,k; int arr[200005][4]; vector<pair<int,int> > ans; bool sc(int nk){ if(nk==0){ for(int i=0; i<n; i++) if(arr[i][0]!=-1) return false; return true; } int hm[4]={-1,-1,(int)1e9,(int)1e9}; for(int i=0; i<n; i++){ if(arr[i][0]==-1) continue; for(int j=0; j<2; j++){ hm[j]=max(hm[j],arr[i][j]); } for(int j=2; j<4; j++){ hm[j]=min(hm[j],arr[i][j]); } } pair<int,int> pt; vector<pair<int,int> > undo; pt={hm[0],hm[1]}; ans.push_back(pt); for(int i=0; i<n; i++){ if(arr[i][0]==-1) continue; if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){ undo.push_back({i,arr[i][0]}); arr[i][0]=-1; } } if(sc(nk-1)) return true; ans.pop_back(); for(auto i:undo) arr[i.first][0]=i.second; undo.clear(); pt={hm[2],hm[1]}; ans.push_back(pt); for(int i=0; i<n; i++){ if(arr[i][0]==-1) continue; if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){ undo.push_back({i,arr[i][0]}); arr[i][0]=-1; } } if(sc(nk-1)) return true; ans.pop_back(); for(auto i:undo) arr[i.first][0]=i.second; undo.clear(); pt={hm[2],hm[3]}; ans.push_back(pt); for(int i=0; i<n; i++){ if(arr[i][0]==-1) continue; if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){ undo.push_back({i,arr[i][0]}); arr[i][0]=-1; } } if(sc(nk-1)) return true; ans.pop_back(); for(auto i:undo) arr[i.first][0]=i.second; undo.clear(); pt={hm[0],hm[3]}; ans.push_back(pt); for(int i=0; i<n; i++){ if(arr[i][0]==-1) continue; if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){ undo.push_back({i,arr[i][0]}); arr[i][0]=-1; } } if(sc(nk-1)) return true; ans.pop_back(); for(auto i:undo) arr[i.first][0]=i.second; undo.clear(); return false; } bool delpt(pair<int,int> pt){ vector<pair<int,int> > undo; ans.push_back(pt); for(int i=0; i<n; i++){ if(arr[i][0]==-1) continue; if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){ undo.push_back({i,arr[i][0]}); arr[i][0]=-1; } } if(sc(3)) return true; ans.pop_back(); for(auto i:undo) arr[i.first][0]=i.second; undo.clear(); return false; } unordered_set<int> us; void s4(){ int hm[4]={-1,-1,(int)1e9,(int)1e9}; for(int i=0; i<n; i++){ if(arr[i][0]==-1) continue; for(int j=0; j<2; j++){ hm[j]=max(hm[j],arr[i][j]); } for(int j=2; j<4; j++){ hm[j]=min(hm[j],arr[i][j]); } } for(int i:us){ pair<int,int> pt; pt={hm[0],i}; if(delpt(pt)) return; pt={hm[2],i}; if(delpt(pt)) return; pt={i,hm[1]}; if(delpt(pt)) return; pt={i,hm[3]}; if(delpt(pt)) return; } } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for(int i=0; i<n; i++) for(int j=0; j<4; j++){ cin >> arr[i][j]; us.insert(arr[i][j]); } if(sc(k)){ for(auto i:ans) cout << i.first << ' ' << i.second << '\n'; } else{ ans.clear(); s4(); for(auto i:ans) cout << i.first << ' ' << i.second << '\n'; } }
#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...