| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 778952 |
2023-07-11T05:07:00 Z |
이동현(#10002) |
Tram (CEOI13_tram) |
C++17 |
|
123 ms |
22652 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
set<pair<int, int>> use, emp;
priority_queue<vector<int>> pq;
vector<vector<int>> pos(q);
auto nxtrow = [&](int x){
auto p = use.lower_bound(make_pair(x, -1));
if(p != use.end()) return p->first;
return (int)1e9;
};
auto prerow = [&](int x){
auto p = use.lower_bound(make_pair(x + 1, -1));
if(p == use.begin()) return -(int)1e9;
--p;
return p->first;
};
auto getdist = [&](int x, int y){
int rv = (int)1e18;
auto p = use.lower_bound(make_pair(x, y));
auto q = p;
for(int rep = 0; rep < 2 && p != use.end(); ++rep, ++p){
rv = min(rv, (x - p->first) * (x - p->first) + (y != p->second));
}
for(int rep = 0; rep < 2 && q != use.begin(); ++rep){
--q;
rv = min(rv, (x - q->first) * (x - q->first) + (y != q->second));
};
return rv;
};
auto push = [&](int up, int down){
if(up + 2 > down){
return;
}
if(down == (int)1e9 && up == n - 1) return;
if(up == -(int)1e9 && down == 0) return;
int uchk[2] = {0, 0};
int dchk[2] = {0, 0};
auto p = use.lower_bound(make_pair(up, -1));
if(p != use.end() && p->first == up) uchk[p->second] = 1;
if(p != use.end()){
++p;
if(p != use.end() && p->first == up) uchk[p->second] = 1;
}
p = use.lower_bound(make_pair(down, -1));
if(p != use.end() && p->first == down) dchk[p->second] = 1;
if(p != use.end()){
++p;
if(p != use.end() && p->first == down) dchk[p->second] = 1;
}
int dist = (up - down) / 2 * ((up - down) / 2);
int xp = (up + down) / 2;
if(down == (int)1e9){
dist = (n - up - 1) * (n - up - 1);
xp = n - 1;
}
if(up == -(int)1e9){
xp = 0;
dist = down * down;
}
// cout << "PUSH " << up << ' ' << down << ' ' << dist << endl;
// cout << uchk[0] << ' ' << uchk[1] << ' ' << dchk[0] << ' ' << dchk[1] << endl;
if(up == -(int)1e9 || down == (int)1e9 || (down - up) % 2 == 0){
if(!uchk[0] && !dchk[0]){
if(dist + 1 > 1) pq.push({dist + 1, -xp, 0});
}
else if(!uchk[1] && !dchk[1]){
if(dist + 1 > 1) pq.push({dist + 1, -xp, -1});
}
else{
if(dist > 1) pq.push({dist, -xp, 0});
}
}
else{
if(!uchk[0]){
if(dist + 1 > 1) pq.push({dist + 1, -xp, 0});
}
else if(!uchk[1]){
if(dist + 1 > 1) pq.push({dist + 1, -xp, -1});
}
else if(!dchk[0]){
if(dist + 1 > 1) pq.push({dist + 1, -(xp + 1), 0});
}
else if(!dchk[1]){
if(dist + 1 > 1) pq.push({dist + 1, -(xp + 1), -1});
}
else{
if(dist > 1) pq.push({dist, -xp, 0});
}
}
};
for(int i = 0; i < n; ++i){
emp.insert({i, 0});
emp.insert({i, 1});
}
for(int rep = 0; rep < q; ++rep){
char c;
cin >> c;
if(c == 'E'){
int x = 0, y = 0;
if((int)use.size()){
int did = 0;
while(!pq.empty()){
int dist = pq.top()[0];
x = -pq.top()[1], y = -pq.top()[2];
// cout << "PQ " << dist << ' ' << x << ' ' << y << endl;
pq.pop();
if(getdist(x, y) == dist){
did = 1;
break;
}
}
if(!did){
x = emp.begin()->first;
y = emp.begin()->second;
}
}
cout << x + 1 << ' ' << y + 1 << '\n';
emp.erase(make_pair(x, y));
use.insert(make_pair(x, y));
pos[rep] = {x, y};
push(x, nxtrow(x + 1));
push(prerow(x - 1), x);
}
else{
int id;
cin >> id;
--id;
int x = pos[id][0], y = pos[id][1];
use.erase(make_pair(x, y));
emp.insert(make_pair(x, y));
push(prerow(x), nxtrow(x + 1));
push(prerow(x - 1), nxtrow(x));
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
580 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
576 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
19180 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
50 ms |
19156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
19264 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
51 ms |
19148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
4164 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
36 ms |
3964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
22652 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1892 KB |
Output is correct |
| 3 |
Correct |
114 ms |
21196 KB |
Output is correct |
