| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 328884 |
2020-11-18T10:47:00 Z |
HCl_10 |
Tram (CEOI13_tram) |
C++14 |
|
55 ms |
6380 KB |
/* by Hyperhydrochloric Acid */
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define loop(i, n) for(int i = 0; i < (n); ++i)
#define cont(i, n) for(int i = 1; i <= (n); ++i)
#define circ(i, a, b) for(int i = (a); i <= (b); ++i)
#define range(i, a, b, c) for(int i = (a); ((c) > 0 ? i <= (b) : i >= (b)); i += (c))
#define foreach(it, v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
#define y0 y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1 y1II11II11III11I1III11II111IIII1II1I1
#define pub push_back
#define pob pop_back
#define mak make_pair
typedef long long ll;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */
int inline Dist(int x, int y) {
return x * x + y * y;
}
struct Cand {
int x, y;
int dist;
Cand(int x, int y, int dist): x(x), y(y), dist(dist) {}
bool operator<(const Cand &c) const {
return mak(dist, mak(-x, -y)) < mak(c.dist, mak(-c.x, -c.y));
}
};
int n, m;
set<Cand> T;
set<int> S;
int x[1 << 18], y[1 << 18];
int lgl[1 << 18];
void inline change(int l, int r, int mode) {
if(!~l && !~r) return;
if(!~l) {
if(r == 1) return;
Cand c(1, 1 + (lgl[r] == 1), Dist(r - 1, lgl[r] != 3));
if(mode) T.insert(c);
else T.erase(c);
} else if(!~r) {
if(l == n) return;
Cand c(n, 1 + (lgl[l] == 1), Dist(n - l, lgl[l] != 3));
if(mode) T.insert(c);
else T.erase(c);
} else {
if(l + 1 == r) return;
int mid = (l + r) >> 1;
Cand mx(-1, -1, -Inf);
loop(th, 2) {
int nx = mid + th;
if(nx >= r) continue;
loop(ny, 2) {
Cand cd(nx, ny + 1, min(Dist(nx - l, !((lgl[l] >> ny) & 1)), Dist(r - nx, !((lgl[r] >> ny) & 1))));
mx = max(mx, cd);
}
}
if(mode) T.insert(mx);
else T.erase(mx);
}
}
int inline prev(int x) {
set<int>::iterator it = S.lower_bound(x);
if(it == S.begin()) return -1;
else return *--it;
}
int inline succ(int x) {
set<int>::iterator it = S.upper_bound(x);
if(it == S.end()) return -1;
else return *it;
}
// mode: 0 -- Erase, 1 -- Insert; update area between prev(x) and succ(x)
void inline control(int x, int mode) {
int l = prev(x), r = succ(x);
if(lgl[x]) change(l, x, mode), change(x, r, mode);
else change(l, r, mode);
if(lgl[x] == 1) {
if(mode) T.insert(Cand(x, 2, 1));
else T.erase(Cand(x, 2, 1));
}
if(lgl[x] == 2) {
if(mode) T.insert(Cand(x, 1, 1));
else T.erase(Cand(x, 1, 1));
}
}
int main() {
scanf("%d%d", &n, &m);
cont(i, m) {
char s; scanf(" %c", &s);
if(s == 'E') {
Cand cc(1, 1, 1);
if(SZ(T)) {
cc = *--T.end();
T.erase(cc);
}
printf("%d %d\n", cc.x, cc.y);
x[i] = cc.x, y[i] = cc.y;
control(x[i], 0);
lgl[x[i]] |= 1 << (y[i] - 1);
if(lgl[x[i]]) S.insert(x[i]);
control(x[i], 1);
} else {
int t; scanf("%d", &t);
int X = x[t], Y = y[t];
control(X, 0);
lgl[X] ^= 1 << (Y - 1);
if(!lgl[X]) S.erase(Y);
control(X, 1);
}
}
return 0;
}
/**
* 思考时间：17:00-18:00, 1h
* 实现时间：
* 实现思路
* 维护两个 set，分别表示有人的位置 S 和每一个可行的位置及与周围的距离 T
* 查找的时候，直接使用 T 的最后一个元素
* 修改的时候，对于一个插入操作，将插入的位置从 T 中删除，加入 S，并修改 T 的两端。
* 对于一个删除操作，将删除的位置从 S 中删除，并加入 T。
*/
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
98 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:100:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | char s; scanf(" %c", &s);
| ~~~~~^~~~~~~~~~~
tram.cpp:114:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
114 | int t; scanf("%d", &t);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
2284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
6380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
