#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const ll INFF = (ll)1e18;
const int INF = (int)1e9;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
auto sq = [&](int d1, int d2)->ll{
return 1ll * d1 * d1 + 1ll * d2 * d2;
};
auto get_mid = [&](array<int, 2> f, array<int, 2> s)->array<ll, 3>{ // [row, mask col] -> return
array<int, 2> nl = {-1, -1};
if(f == nl && s == nl){
return {INFF, 1, 0};
}
array<ll, 3> res;
res[0] = -1;
if(f == nl){
REP(c, 2){
ll dist = INFF;
REP(g, 2){
if(s[1] & (1 << g)){
dist = min(dist, sq(s[0] - 1, g - c));
}
}
if((dist > res[0]) || (dist == res[0] && c < res[2])){
res[0] = dist;
res[1] = 1;
res[2] = c;
}
}
return res;
}
if(s == nl){
REP(c, 2){
ll dist = INFF;
REP(g, 2){
if(f[1] & (1 << g)){
dist = min(dist, sq(f[0] - n, g - c));
}
}
if((dist > res[0]) || (dist == res[0] && c < res[2])){
res[0] = dist;
res[1] = n;
res[2] = c;
}
}
return res;
}
int m = (f[0] + s[0]) / 2;
FOR(d, -1, 2, 1){
int nr = m + d;
if(nr < f[0] || nr > s[0])
continue;
REP(nc, 2){
ll dist = INFF;
REP(g, 2){
if((f[1] & (1 << g))){
ll tm = sq(f[0] - nr, nc - g);
dist = min(dist, tm);
}
if((s[1] & (1 << g))){
ll tm = sq(s[0] - nr, nc - g);
dist = min(dist, tm);
}
}
if((dist > res[0]) || (dist == res[0] && nr < res[1]) || (dist == res[0] && nr == res[1] && nc < res[2])){
res[0] = dist;
res[1] = nr;
res[2] = nc;
}
}
}
return res;
};
auto cmp = [&](array<ll, 3> f, array<ll, 3> s){
if(f[0] == s[0]){
return tie(f[1], f[2]) < tie(s[1], s[2]);
}
else{
return f[0] > s[0];
}
};
set<array<ll, 3>, decltype(cmp)> pq(cmp);
pq.insert(get_mid({-1, -1}, {-1, -1}));
set<array<int, 2>> occupied;
vector<array<int, 2>> mapka(m);
auto get_next = [&](int row)->array<int, 2>{
auto it = occupied.lower_bound({row + 1, -1});
if(it == occupied.end()){
return {-1, -1};
}
else{
return *it;
}
};
auto get_prev = [&](int row)->array<int, 2>{
auto it = occupied.lower_bound({row, -1});
if(it == occupied.begin()){
return {-1, -1};
}
else{
it--;
return *it;
}
};
REP(i, m){
char e;
cin >> e;
if(e == 'E'){
auto v = *pq.begin();
pq.erase(pq.begin());
auto it = occupied.lower_bound({v[1], 0});
mapka[i] = {v[1], v[2]};
array<int, 2> tm;
if(it != occupied.end() && (*it)[0] == v[1]){
tm = (*it);
occupied.erase(it);
tm[1] |= (1 << v[2]);
occupied.insert(tm);
}
else{
tm = {v[1], (1 << v[2])};
occupied.insert(tm);
}
pq.insert(get_mid(tm, get_next(v[1])));
pq.insert(get_mid(get_prev(v[1]), tm));
cout << v[1] << " " << v[2] + 1 << "\n";
}
else{
int id;
cin >> id;
id--;
auto temp = *occupied.lower_bound({mapka[id][0], -1});
pq.erase(get_mid(temp, get_next(mapka[id][0])));
pq.erase(get_mid(get_prev(mapka[id][0]), temp));
auto it = occupied.lower_bound({mapka[id][0], -1});
array<int, 2> tm;
if((*it)[1] == 3){
tm = (*it);
occupied.erase(it);
tm[1] &= (~(1 << mapka[id][1]));
occupied.insert(tm);
}
else{
tm = {-1, -1};
occupied.erase(it);
}
array<int, 2> nl = {-1, -1};
int r = mapka[id][0];
if(tm == nl){
pq.insert(get_mid(get_prev(r), get_next(r)));
}
else{
pq.insert(get_mid(tm, get_next(r)));
pq.insert(get_mid(get_prev(r), tm));
}
}
}
return 0;
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:125:53: warning: narrowing conversion of 'v.std::array<long long int, 3>::operator[](1)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
125 | auto it = occupied.lower_bound({v[1], 0});
| ^
tram.cpp:126:35: warning: narrowing conversion of 'v.std::array<long long int, 3>::operator[](1)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
126 | mapka[i] = {v[1], v[2]};
| ^
tram.cpp:126:35: warning: narrowing conversion of 'v.std::array<long long int, 3>::operator[](2)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
tram.cpp:135:40: warning: narrowing conversion of 'v.std::array<long long int, 3>::operator[](1)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
135 | tm = {v[1], (1 << v[2])};
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Correct |
4 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
316 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
31 ms |
2388 KB |
Output is correct |
| 2 |
Correct |
39 ms |
844 KB |
Output is correct |
| 3 |
Correct |
41 ms |
1612 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
56 ms |
4028 KB |
Output is correct |
| 2 |
Correct |
42 ms |
848 KB |
Output is correct |
| 3 |
Correct |
34 ms |
1612 KB |
Output is correct |
