oj.uz

답안 #778952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778952 2023-07-11T05:07:00 Z 이동현(#10002) 전차 (CEOI13_tram) C++17
100 / 100
 123 ms 22652 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    set<pair<int, int>> use, emp;
    priority_queue<vector<int>> pq;
    vector<vector<int>> pos(q);

    auto nxtrow = [&](int x){
        auto p = use.lower_bound(make_pair(x, -1));
        if(p != use.end()) return p->first;
        return (int)1e9;
    };
    auto prerow = [&](int x){
        auto p = use.lower_bound(make_pair(x + 1, -1));
        if(p == use.begin()) return -(int)1e9;
        --p;
        return p->first;
    };
    auto getdist = [&](int x, int y){
        int rv = (int)1e18;
        auto p = use.lower_bound(make_pair(x, y));
        auto q = p;
        for(int rep = 0; rep < 2 && p != use.end(); ++rep, ++p){
            rv = min(rv, (x - p->first) * (x - p->first) + (y != p->second));
        }
        for(int rep = 0; rep < 2 && q != use.begin(); ++rep){
            --q;
            rv = min(rv, (x - q->first) * (x - q->first) + (y != q->second));
        };
        return rv;
    };
    auto push = [&](int up, int down){
        if(up + 2 > down){
            return;
        }
        if(down == (int)1e9 && up == n - 1) return;
        if(up == -(int)1e9 && down == 0) return;

        int uchk[2] = {0, 0};
        int dchk[2] = {0, 0};
        auto p = use.lower_bound(make_pair(up, -1));
        if(p != use.end() && p->first == up) uchk[p->second] = 1;
        if(p != use.end()){
            ++p;
            if(p != use.end() && p->first == up) uchk[p->second] = 1;
        }

        p = use.lower_bound(make_pair(down, -1));
        if(p != use.end() && p->first == down) dchk[p->second] = 1;
        if(p != use.end()){
            ++p;
            if(p != use.end() && p->first == down) dchk[p->second] = 1;
        }

        int dist = (up - down) / 2 * ((up - down) / 2);
        int xp = (up + down) / 2;
        if(down == (int)1e9){
            dist = (n - up - 1) * (n - up - 1);
            xp = n - 1;
        }
        if(up == -(int)1e9){
            xp = 0;
            dist = down * down;
        }

        // cout << "PUSH " << up << ' ' << down << ' ' << dist << endl;
        // cout << uchk[0] << ' ' << uchk[1] << ' ' << dchk[0] << ' ' << dchk[1] << endl;
        if(up == -(int)1e9 || down == (int)1e9 || (down - up) % 2 == 0){
            if(!uchk[0] && !dchk[0]){
                if(dist + 1 > 1) pq.push({dist + 1, -xp, 0});
            }
            else if(!uchk[1] && !dchk[1]){
                if(dist + 1 > 1) pq.push({dist + 1, -xp, -1});
            }
            else{
                if(dist > 1) pq.push({dist, -xp, 0});
            }
        }
        else{
            if(!uchk[0]){
                if(dist + 1 > 1) pq.push({dist + 1, -xp, 0});
            }
            else if(!uchk[1]){
                if(dist + 1 > 1) pq.push({dist + 1, -xp, -1});
            }
            else if(!dchk[0]){
                if(dist + 1 > 1) pq.push({dist + 1, -(xp + 1), 0});
            }
            else if(!dchk[1]){
                if(dist + 1 > 1) pq.push({dist + 1, -(xp + 1), -1});
            }
            else{
                if(dist > 1) pq.push({dist, -xp, 0});
            }
        }
    };

    for(int i = 0; i < n; ++i){
        emp.insert({i, 0});
        emp.insert({i, 1});
    }

    for(int rep = 0; rep < q; ++rep){
        char c;
        cin >> c;
        if(c == 'E'){
            int x = 0, y = 0;
            if((int)use.size()){
                int did = 0;
                while(!pq.empty()){
                    int dist = pq.top()[0];
                    x = -pq.top()[1], y = -pq.top()[2];
                    // cout << "PQ " << dist << ' ' << x << ' ' << y << endl;
                    pq.pop();
                    if(getdist(x, y) == dist){
                        did = 1;
                        break;
                    }
                }
                if(!did){
                    x = emp.begin()->first;
                    y = emp.begin()->second;
                }
            }
            
            cout << x + 1 << ' ' << y + 1 << '\n';

            emp.erase(make_pair(x, y));
            use.insert(make_pair(x, y));
            pos[rep] = {x, y};
            push(x, nxtrow(x + 1));
            push(prerow(x - 1), x);
        }
        else{
            int id;
            cin >> id;
            --id;
            int x = pos[id][0], y = pos[id][1];
            use.erase(make_pair(x, y));
            emp.insert(make_pair(x, y));
            push(prerow(x), nxtrow(x + 1));
            push(prerow(x - 1), nxtrow(x));
        }
    }
    
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 19180 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 50 ms 19156 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 19264 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 51 ms 19148 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 4164 KB Output is correct
2 Correct 23 ms 1920 KB Output is correct
3 Correct 36 ms 3964 KB Output is correct

Subtask #8
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 22652 KB Output is correct
2 Correct 23 ms 1892 KB Output is correct
3 Correct 114 ms 21196 KB Output is correct