oj.uz

답안 #53266

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53266 2018-06-29T06:22:20 Z 강태규(#1399) 전차 (CEOI13_tram) C++11
100 / 100
 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);
      |             ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 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

Subtask #8
20.0 / 20.0

# 결과 실행 시간 메모리 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