Submission #681062

#TimeUsernameProblemLanguageResultExecution timeMemory
681062Cross_RatioTram (CEOI13_tram)C++14
0 / 100
1097 ms1612 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int INF = 1e18; int A[150005][4]; array<int, 2> B[30005]; set<int> S; int dis(int a, int b, int c, int d) { if(A[a][b]) return 0; if(A[c][d]==0) return INF; return (a-c)*(a-c)+(b-d)*(b-d); } int ma = -1, ix = -1, iy = -1; void calc(int a, int b, int c) { if(ma<a) { ma = a, ix = b, iy = c; } else if(ma==a&&b<ix) { ix = b, iy = c; } else if(ma==a&&b==ix&&c<iy) { iy = c; } } int dist[150005][4]; set<array<int, 3>> S2; int get_dis(int a, int b) { int d = INF; if(A[a][b]) d = min(d, 0LL); if(A[a-1][b]||A[a+1][b]||A[a][b-1]||A[a][b+1]) d = min(d, 1LL); if(!S.empty()) { auto it = S.lower_bound(a); if(it != S.end()) { d = min(d, dis(a, b, *it, 1)); d = min(d, dis(a, b, *it, 2)); } if(it != S.begin()) { it--; d = min(d, dis(a, b, *it, 1)); d = min(d, dis(a, b, *it, 2)); } } return d; } void recalc(int a, int b) { S2.erase({-dist[a][b], a, b}); dist[a][b] = get_dis(a, b); //cout << "Recalced : " << a << ' ' << b << " , " << dist[a][b] << '\n'; S2.insert({-dist[a][b], a, b}); } void del(int a, int b) { S2.erase({-dist[a][b], a, b}); } signed main() { //cin.sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M; int i, j; for(i=0;i<M;i++) B[i] = {-1,-1}; for(j=0;j<M;j++) { string s1; cin >> s1; if(s1=="E") { ma = -1, ix = -1, iy = -1; if(S.empty()) { B[j] = {1, 1}; cout << B[j][0] << ' ' << B[j][1] << '\n'; A[1][1] = 1; S.insert(1); continue; } for(i=1;i<=N;i++) { for(int k = 1; k <= 2;k++) { if(A[i][k]==0) { calc(get_dis(i, k), i, k); } } } cout << ix << ' ' << iy << '\n'; A[ix][iy] = 1; S.insert(ix); continue; //cout << "Current S : "; //for(int n : S) cout << n << ' '; //cout << '\n'; for(i=1;i<=2;i++) { if(A[1][i]==0) { int d = INF; int k = *S.begin(); d = min(d, dis(1, i, k, 1)); d = min(d, dis(1, i, k, 2)); calc(d, 1, i); } } for(i=1;i<=2;i++) { if(A[N][i]==0) { int d = INF; int k = *S.rbegin(); d = min(d, dis(N, i, k, 1)); d = min(d, dis(N, i, k, 2)); calc(d, N, i); } } //cout << "Current Max : " << ma << ' ' << ix <<' ' << iy << '\n'; while(!S2.empty()) { auto it = *S2.begin(); //cout << "Is right? : " << -it[0] << ' ' << it[1] << ' ' << it[2] << '\n'; if(A[it[1]][it[2]]) { S2.erase(it); } else if(get_dis(it[1], it[2]) != -it[0]) { recalc(it[1], it[2]); } else break; } if(!S2.empty()) { auto it = *S2.begin(); calc(-it[0], it[1], it[2]); //cout << -it[0] << ' ' << it[1] << ' ' << it[2] << '\n'; } if(ma <= 1) { int dx = -1, dy = -1; for(i=1;i<=N;i++) { for(int k = 1; k <= 2; k++) { if(A[i][k]==0) { dx = i, dy = k; break; } } if(dx!=-1) break; } calc(1, dx, dy); } if(A[ix][3-iy]==0) { int x = ix, y = 3 - iy; calc(get_dis(x, 3-y), x, 3-y); //cout << get_dis(x, y) << ' ' << x << ' '<< 3 - y << '\n' } B[j] = {ix, iy}; cout << ix << ' ' << iy << '\n'; assert(A[ix][iy]==0); A[ix][iy] = 1; if(S.find(ix)==S.end()) { auto it = S.lower_bound(ix); if(it != S.begin()) { auto it2 = it; it2--; int low = *it2, high = *it; int d = (low + high) / 2; del(d, 1); del(d, 2); if(low%2!=high%2) { del(d+1, 1); del(d+1, 2); } } } S.insert(ix); auto it = S.lower_bound(ix); if(it != S.begin()) { auto it2 = it; it2--; int low = *it2; int d1 = (low + ix) / 2; recalc(d1, 1), recalc(d1, 2); if(low%2!=ix%2) { recalc(d1+1, 1), recalc(d1+1, 2); } } it++; if(it!=S.end()) { int d1 = (ix + *it) / 2; recalc(d1, 1), recalc(d1, 2); if(ix%2!=*it%2) { recalc(d1+1, 1), recalc(d1+1, 2); } } } if(s1=="L") { int k; cin >> k; k--; A[B[k][0]][B[k][1]] = 0; //cout << "Erase : " << B[k][0] << ' ' << B[k][1] << '\n'; ix = B[k][0]; auto it = S.lower_bound(ix); vector<array<int , 2>> VC; if(it != S.begin()) { auto it2 = it; it2--; int low = *it2; int d1 = (low + ix) / 2; VC.push_back({d1, 1}); VC.push_back({d1, 2}); if(low%2!=ix%2) { VC.push_back({d1+1, 1}); VC.push_back({d1+1, 2}); } } it++; if(it!=S.end()) { int d1 = (ix + *it) / 2; VC.push_back({d1, 1}); VC.push_back({d1, 2}); if(ix%2!=*it%2) { VC.push_back({d1+1, 1}); VC.push_back({d1+1, 2}); } } if(A[B[k][0]][3-B[k][1]]==0) { S.erase(B[k][0]); for(auto it : VC) del(it[0], it[1]); if(S.size() >= 2) { auto it = S.lower_bound(ix); if(it!=S.begin() && it != S.end()) { auto it2 = it; it2--; int low = *it2, high = *it; int d = (low +high) / 2; recalc(d, 1), recalc(d, 2); if(low%2!=high%2) { recalc(d+1, 1), recalc(d+1, 2); } } } } else { for(auto it : VC) recalc(it[0], it[1]); } } } }
#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...