oj.uz

Submission #258720

# Submission time Handle Problem Language Result Execution time Memory
258720 2020-08-06T12:20:53 Z dolphingarlic Tram (CEOI13_tram) C++14
10 / 100
 59 ms 4460 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, m;
bool used[150001][3];

ll dist(pair<int, int> A, pair<int, int> B) {
    return ll(B.first - A.first) * ll(B.first - A.first) +
           ll(B.second - A.second) * ll(B.second - A.second);
}

struct Interval {
    int l, r;
    ll best_dist;
    pair<int, int> best_pos;

    void update() {
        best_dist = -1;
        int mid1 = (l + r) / 2, mid2 = (l + r + 1) / 2;
        vector<pair<int, int>> cand = {{l, 1},    {l, 2},    {mid1, 1}, {mid1, 2},
                                       {mid2, 1}, {mid2, 2},  {r, 1},   {r, 2}};
        for (pair<int, int> j : cand) {
            if (!used[j.first][j.second]) {
                ll d = LLONG_MAX;
                for (pair<int, int> k : cand) {
                    if (used[k.first][k.second]) {
                        d = min(d, dist(j, k));
                    }
                }
                if (d > best_dist && (d != LLONG_MAX || (l == 1 && r == n))) {
                    best_dist = d;
                    best_pos = j;
                }
            }
        }
    }
};
bool operator<(Interval A, Interval B) {
    return (A.best_dist == B.best_dist ? A.best_pos < B.best_pos : A.best_dist > B.best_dist);
}

pair<int, int> pos[30001];
set<int> hmmst;
set<Interval> intervals;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    hmmst.insert(1);
    hmmst.insert(n);
    Interval i = {1, n, LLONG_MAX, {1, 1}};
    intervals.insert(i);

    for (int i = 1; i <= m; i++) {
        char c;
        cin >> c;
        if (c == 'E') {
            Interval opt = *intervals.begin();
            intervals.erase(opt);
            pos[i] = opt.best_pos;
            used[pos[i].first][pos[i].second] = true;
            hmmst.insert(pos[i].first);
            if (pos[i].first != opt.l && pos[i].first != opt.r) {
                Interval A = {opt.l, pos[i].first, 0, {0, 0}}, B = {pos[i].first, opt.r, 0, {0, 0}};
                A.update(), B.update();
                intervals.insert(A), intervals.insert(B);
            } else {
                opt.update();
                intervals.insert(opt);
            }
            cout << pos[i].first << ' ' << pos[i].second << '\n';
        } else {
            int idx;
            cin >> idx;
            if (pos[idx].first == 1) {
                int r = *next(hmmst.find(1));
                Interval A = {1, r, 0, {0, 0}};
                A.update();
                intervals.erase(A);
                used[pos[idx].first][pos[idx].second] = false;
                A.update();
                intervals.insert(A);
            } else if (pos[idx].first == n) {
                int l = *prev(hmmst.find(n));
                Interval A = {l, n, 0, {0, 0}};
                A.update();
                intervals.erase(A);
                used[pos[idx].first][pos[idx].second] = false;
                A.update();
                intervals.insert(A);
            } else {
                int l = *prev(hmmst.find(pos[idx].first)), r = *next(hmmst.find(pos[idx].first));
                Interval A = {l, pos[idx].first, 0, {0, 0}}, B = {pos[idx].first, r, 0, {0, 0}};
                A.update(), B.update();
                intervals.erase(A), intervals.erase(B);
                used[pos[idx].first][pos[idx].second] = false;
                    
                if (!used[pos[idx].first][1] && !used[pos[idx].first][2]) {
                    Interval C = {l, r, 0, {0, 0}};
                    C.update();
                    intervals.insert(C);
                    hmmst.erase(pos[idx].first);
                } else {
                    A.update(), B.update();
                    intervals.insert(A), intervals.insert(B);
                }
            }
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Incorrect 2 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Incorrect 2 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1004 KB Output is correct
2 Incorrect 2 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1004 KB Output is correct
2 Incorrect 2 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2156 KB Output is correct
2 Incorrect 32 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4460 KB Output is correct
2 Incorrect 31 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -