| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 681077 |
2023-01-12T10:28:27 Z |
Cross_Ratio |
Tram (CEOI13_tram) |
C++14 |
|
592 ms |
17740 KB |
#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;
}
if(N <= 1500) {
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;
B[j] = {ix, iy};
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'
}
if(ma >= 3 && S.size() <= 300) {
int pv = -1;
for(int n : S) {
if(pv==-1) {
pv = n;
continue;
}
int sq = sqrt(ma);
for(int k = pv + sq; k <= n - sq; k++) {
if(A[k][1]==0) calc(get_dis(k, 1), k, 1);
if(A[k][2]==0) calc(get_dis(k, 2), k, 2);
}
pv = 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 time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
476 KB |
Output is correct |
| 2 |
Correct |
5 ms |
340 KB |
Output is correct |
| 3 |
Correct |
77 ms |
408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
492 KB |
Output is correct |
| 2 |
Correct |
6 ms |
340 KB |
Output is correct |
| 3 |
Correct |
69 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
4 ms |
340 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
9664 KB |
Output is correct |
| 2 |
Correct |
4 ms |
392 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
4400 KB |
Output is correct |
| 2 |
Correct |
592 ms |
1224 KB |
Output is correct |
| 3 |
Correct |
72 ms |
3532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
17740 KB |
Output is correct |
| 2 |
Correct |
547 ms |
1104 KB |
Output is correct |
| 3 |
Correct |
87 ms |
12336 KB |
Output is correct |
