| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 779065 |
2023-07-11T07:15:08 Z |
이성호(#10001) |
Tram (CEOI13_tram) |
C++17 |
|
49 ms |
10652 KB |
#include <iostream>
#include <set>
#define int long long
using namespace std;
const int inf = 1e18;
struct State
{
int r, c;
int dis;
bool operator<(const State &st) const
{
if (dis != st.dis) return dis < st.dis;
if (r != st.r) return r > st.r;
else return c > st.c;
}
};
int cal(int r, int c, int r0, int c0)
{
return (r - r0) * (r - r0) + (c - c0) * (c - c0);
}
int get_dis(int r, int c, int r1, int s1, int r2, int s2)
{
int ans = inf;
if (s1 & 1) ans = min(ans, cal(r, c, r1, 1));
if (s1 & 2) ans = min(ans, cal(r, c, r1, 2));
if (s2 & 1) ans = min(ans, cal(r, c, r2, 1));
if (s2 & 2) ans = min(ans, cal(r, c, r2, 2));
return ans;
}
int get_dis2(int r, int c, int r1, int s1)
{
int ans = inf;
if (s1 & 1) ans = min(ans, cal(r, c, r1, 1));
if (s1 & 2) ans = min(ans, cal(r, c, r1, 2));
return ans;
}
int N;
set<pair<int, int>> st;
set<State> cand;
void put(int r1, int s1, int r2, int s2)
{
if (r2 > r1 + 1) {
for (int nr = (r1 + r2) / 2; nr <= (r1 + r2 + 1) / 2; nr++) {
State state; state.r = nr, state.c = 1, state.dis = get_dis(nr, 1, r1, s1, r2, s2);
State state2; state2.r = nr, state2.c = 2, state2.dis = get_dis(nr, 2, r1, s1, r2, s2);
cand.insert(state); cand.insert(state2);
}
}
}
void era(int r1, int s1, int r2, int s2)
{
if (r2 > r1 + 1) {
for (int nr = (r1 + r2) / 2; nr <= (r1 + r2 + 1) / 2; nr++) {
State state; state.r = nr, state.c = 1, state.dis = get_dis(nr, 1, r1, s1, r2, s2);
State state2; state2.r = nr, state2.c = 2, state2.dis = get_dis(nr, 2, r1, s1, r2, s2);
cand.erase(state); cand.erase(state2);
}
}
}
void ins(int r, int s) //(r, s)�� ����
{
if (st.empty()) {
st.insert(make_pair(1, 1));
State s1; s1.dis = 1, s1.r = 1, s1.c = 2; cand.insert(s1);
State s2; s2.dis = (N-1)*(N-1), s2.r = N, s2.c = 1; cand.insert(s2);
State s3; s3.dis = (N-1)*(N-1)+1, s3.r = N, s3.c = 2; cand.insert(s3);
return;
}
auto it = st.lower_bound(make_pair(r, 0));
int r2 = -1, s2 = -1, r0 = -1, s0 = -1;
if (it != st.end()) {
r2 = (*it).first, s2 = (*it).second;
}
else {
--it;
int tr = (*it).first, ts = (*it).second;
State s1; s1.r = N, s1.c = 1, s1.dis = get_dis2(N, 1, tr, ts);
State s2; s2.r = N, s2.c = 2, s2.dis = get_dis2(N, 2, tr, ts);
cand.erase(s1); cand.erase(s2);
++it;
if (r != N) {
s1.dis = get_dis2(N, 1, r, s); s2.dis = get_dis2(N, 2, r, s);
cand.insert(s1); cand.insert(s2);
}
}
if (it != st.begin()) {
--it;
r0 = (*it).first, s0 = (*it).second;
++it;
}
else {
int tr = (*it).first, ts = (*it).second;
State s1; s1.r = 1; s1.c = 1; s1.dis = get_dis2(1, 1, tr, ts);
State s2; s2.r = 1; s2.c = 2; s2.dis = get_dis2(1, 2, tr, ts);
cand.erase(s1); cand.erase(s2);
if (r != 1) {
s1.dis = get_dis2(1, 1, r, s); s2.dis = get_dis2(1, 2, r, s);
cand.insert(s1); cand.insert(s2);
}
}
if (r0 != -1 && r2 != -1) {
era(r0, s0, r2, s2);
}
if (it != st.end()) put(r, s, r2, s2);
if (it != st.begin()) put(r0, s0, r, s);
st.insert(make_pair(r, s));
if (s == 1) {
State state; state.r = r, state.c = 2, state.dis = 1;
cand.insert(state);
}
else if (s == 2) {
State state; state.r = r, state.c = 1, state.dis = 1;
cand.insert(state);
}
}
void del(int r, int s)
{
if (st.size() == 1) {
st.clear();
cand.clear();
return;
}
if (s == 1) {
cand.erase({r, 2, 1});
}
else if (s == 2) {
cand.erase({r, 1, 1});
}
int r0 = -1, s0 = -1, r2 = -1, s2 = -1;
auto it = st.find(make_pair(r, s));
if (++it != st.end()) {
r2 = (*it).first, s2 = (*it).second;
era(r, s, r2, s2);
}
else {
State s1; s1.r = N, s1.c = 1;
State s2; s2.r = N, s2.c = 2;
if (r != N) {
s1.dis = get_dis2(N, 1, r, s); s2.dis = get_dis2(N, 2, r, s);
cand.erase(s1); cand.erase(s2);
}
--it; --it;
int tr = (*it).first, ts = (*it).second;
s1.dis = get_dis2(N, 1, tr, ts); s2.dis = get_dis2(N, 2, tr, ts);
cand.insert(s1); cand.insert(s2);
++it; ++it;
}
--it;
if (it != st.begin()) {
--it;
r0 = (*it).first, s0 = (*it).second;
era(r0, s0, r, s);
++it;
}
else {
State s1; s1.r = 1, s1.c = 1;
State s2; s2.r = 1, s2.c = 2;
if (r != 1) {
s1.dis = get_dis2(1, 1, r, s); s2.dis = get_dis2(1, 2, r, s);
cand.erase(s1); cand.erase(s2);
}
++it;
int tr = (*it).first, ts = (*it).second;
s1.dis = get_dis2(1, 1, tr, ts); s2.dis = get_dis2(1, 2, tr, ts);
cand.insert(s1); cand.erase(s2);
--it;
}
if (r0 != -1 && r2 != -1) {
put(r0, s0, r2, s2);
}
st.erase(it);
}
pair<int, int> mmr[30005];
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int M; cin >> N >> M;
if (N == 1) {
bool s0 = false, s1 = false;
for (int i = 1; i <= M; i++) {
char qr; cin >> qr;
int r = -1, c = -1;
if (qr == 'E') {
if (!s0) {
s0 = true;
r = 1, c = 1;
}
else {
s1 = true;
r = 1, c = 2;
}
mmr[i] = make_pair(r, c);
cout << r << ' ' << c << '\n';
}
else {
int n; cin >> n;
if (mmr[n].second == 1) {
s0 = false;
}
else {
s1 = false;
}
}
}
return 0;
}
for (int i = 1; i <= M; i++) {
char pv; cin >> pv;
if (pv == 'E') {
if (st.empty()) {
ins(1, 1);
cout << 1 << ' ' << 1 << '\n';
mmr[i] = make_pair(1, 1);
continue;
}
auto it = --cand.end();
int r = (*it).r, c = (*it).c;
auto tmp = st.lower_bound(make_pair(r, 0));
if (tmp == st.end() || (*tmp).first != r) {
ins(r, c);
}
else {
del(r, (*tmp).second);
ins(r, 3);
}
mmr[i] = make_pair(r, c);
cout << r << ' ' << c << '\n';
}
else {
int P; cin >> P;
int r = mmr[P].first, c = mmr[P].second;
auto tmp = st.lower_bound(make_pair(r, 0));
if ((*tmp).second == 3) {
del(r, 3);
ins(r, 3 - c);
}
else {
del(r, c);
}
}
}
return 0;
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:179:26: warning: variable 's1' set but not used [-Wunused-but-set-variable]
179 | bool s0 = false, s1 = false;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
724 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
772 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
2848 KB |
Output is correct |
| 2 |
Correct |
27 ms |
980 KB |
Output is correct |
| 3 |
Correct |
32 ms |
2788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
10652 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
904 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
