| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 681015 |
2023-01-12T09:07:15 Z |
Cross_Ratio |
Tram (CEOI13_tram) |
C++14 |
|
230 ms |
23672 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;
map<int, set<array<int, 2>> > M;
int dis(int a, int b, int c, int d) {
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;
void recalc(int a, int b) {
S2.erase({-dist[a][b], a, 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>a) {
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));
}
}
}
dist[a][b] = d;
S2.insert({-d, 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;
}
//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();
if(A[it[1]][it[2]]) {
S2.erase(it);
}
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);
}
B[j] = {ix, iy};
cout << ix << ' ' << iy << '\n';
A[ix][iy] = 1;
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 high = *it;
int d1 = (low + high) / 2;
recalc(d1, 1), recalc(d1, 2);
if(low%2!=high%2) {
recalc(d1+1, 1), recalc(d1+1, 2);
}
}
it--;
}
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);
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 high = *it;
int d1 = (low + high) / 2;
recalc(d1, 1), recalc(d1, 2);
if(low%2!=high%2) {
recalc(d1+1, 1), recalc(d1+1, 2);
}
}
it--;
}
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(A[B[k][0]][3-B[k][1]]==0) S.erase(B[k][0]);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
230 ms |
4580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
158 ms |
23672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
