| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53266 |
2018-06-29T06:22:20 Z |
강태규(#1399) |
Tram (CEOI13_tram) |
C++11 |
|
63 ms |
9980 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
const int inf = 1e6;
int n, m;
int x[30001], y[300001];
int seat[150002];
set<int> mp;
struct st {
int x, y, lp, ls, rp, rs, d;
bool operator<(const st &p) const {
if (d != p.d) return d < p.d;
if (x != p.x) return x > p.x;
return y > p.y;
}
bool valid() const {
if (seat[lp] != ls) return 0;
if (seat[rp] != rs) return 0;
if (*(++mp.find(lp)) != rp) return 0;
return 1;
}
};
priority_queue<st> ev;
void newEvent(int s, int e) {
if (s == 0) {
if (e == n + 1) {
ev.push({ 1, 1, s, seat[s], e, seat[e], inf });
return;
}
int ys = 1, ds = 1;
if (seat[e] == 1) ys = 2;
if (seat[e] & ys) ds = 0;
ev.push({ 1, ys, s, seat[s], e, seat[e], 2 * (e - 1) + ds });
return;
}
if (e == n + 1) {
int ys = 1, ds = 1;
if (seat[s] == 1) ys = 2;
if (seat[s] & ys) ds = 0;
ev.push({ n, ys, s, seat[s], e, seat[e], 2 * (n - s) + ds });
return;
}
for (int i = (s + e - 1) / 2; i <= (s + e + 1) / 2; ++i) {
for (int j = 1; j <= 2; ++j) {
if (seat[i] & j) continue;
int ds = 2 * (i - s) + ((seat[s] & j) ? 0 : 1);
if (i == s) ++ds;
int de = 2 * (e - i) + ((seat[e] & j) ? 0 : 1);
if (i == e) ++de;
int dd = min(ds, de);
ev.push({ i, j, s, seat[s], e, seat[e], dd });
}
}
}
int main() {
char in[10];
scanf("%d%d", &n, &m);
mp.insert(0);
mp.insert(n + 1);
newEvent(0, n + 1);
for (int i = 1; i <= m; ++i) {
scanf("%s", in);
if (in[0] == 'E') {
while (!ev.top().valid()) ev.pop();
st t = ev.top();
ev.pop();
x[i] = t.x;
y[i] = t.y;
if (seat[t.x] == 0) mp.insert(t.x);
seat[t.x] |= t.y;
set<int>::iterator it1 = mp.find(t.x), it2;
it2 = it1;
++it1;
--it2;
newEvent(*it2, t.x);
newEvent(t.x, *it1);
printf("%d %d\n", t.x, t.y);
}
else {
int p;
scanf("%d", &p);
seat[x[p]] &= (y[p] ^ 3);
if (seat[x[p]] == 0) {
mp.erase(x[p]);
set<int>::iterator it1 = mp.lower_bound(x[p]), it2;
it2 = it1;
--it2;
newEvent(*it2, *it1);
}
else {
set<int>::iterator it1 = mp.find(x[p]), it2;
it2 = it1;
++it1;
--it2;
newEvent(*it2, x[p]);
newEvent(x[p], *it1);
}
}
}
return 0;
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%s", in);
| ~~~~~^~~~~~~~~~
tram.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
102 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
748 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
748 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
2704 KB |
Output is correct |
| 2 |
Correct |
32 ms |
1112 KB |
Output is correct |
| 3 |
Correct |
48 ms |
4708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
9980 KB |
Output is correct |
| 2 |
Correct |
38 ms |
1112 KB |
Output is correct |
| 3 |
Correct |
53 ms |
3304 KB |
Output is correct |
