Submission #1198105

#TimeUsernameProblemLanguageResultExecution timeMemory
1198105mychecksedadHamburg Steak (JOI20_hamburg)C++20
2 / 100
1552 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]); } for(int j = 0; j < k; ++j){ int X = 1000000001; int Y = X; vector<array<int, 4>> np; for(auto x: p){ if(X > x[2]){ X = x[2]; Y = x[3]; }else if(X == x[2]){ Y = max(Y, x[3]); } } if(X > 1000000000){ cout << X << ' ' << Y << '\n'; continue; } int l = 1, r = 1000000000, nY = 1; while(l <= r){ int m = l+r>>1; bool ok = true; for(auto x: p){ if(x[0] > X) continue; // out of our range, we don't care if(x[1] <= Y && x[1] > m){ // it's above us, this is bad ok = false; break; } } if(ok){ nY = m; r = m - 1; }else{ l = m + 1; } } Y = nY; for(auto x: p){ if(x[0] <= X && X <= x[2] && x[1] <= Y && Y <= x[3]){ // nothing to do actually }else{ np.pb(x); } } np.swap(p); cout << X << ' ' << Y << '\n'; } if(!p.empty()){ 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...