제출 #413098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413098		ACmachine	전차 (CEOI13_tram)	C++17	0 / 100	42 ms	4112 KiB

tram

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const ll INFF = (ll)1e18;
const int INF = (int)1e9;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    auto sq = [&](int d1, int d2)->ll{
        return 1ll * d1 * d1 + 1ll * d2 * d2;
    };
    auto get_mid = [&](array<int, 2> f, array<int, 2> s)->array<ll, 3>{ // [row, mask col] -> return 
        array<int, 2> nl = {-1, -1};
        if(f == nl && s == nl){
            return {INFF, 1, 0};
        }
        array<ll, 3> res;
        res[0] = -1; 
        if(f == nl){
            REP(c, 2){
                ll dist = INFF;
                REP(g, 2){
                    if(s[1] & (1 << g)){
                        dist = min(dist, sq(s[0] - 1, g - c));
                    }
                }
                if((dist > res[0]) || (dist == res[0] && c < res[2])){
                    res[0] = dist;
                    res[1] = 1;
                    res[2] = c;
                }
            }
            return res;
        }
        if(s == nl){
            REP(c, 2){
                ll dist = INFF;
                REP(g, 2){
                    if(f[1] & (1 << g)){
                        dist = min(dist, sq(f[0] - n, g - c));
                    }
                }
                if((dist > res[0]) || (dist == res[0] && c < res[2])){
                    res[0] = dist;
                    res[1] = n;
                    res[2] = c;
                }
            }
            return res;
        }
        int m = (f[0] + s[0]) / 2;
        FOR(d, -1, 2, 1){
            int nr = m + d;
            if(nr < f[0] || nr > s[0]) 
                continue;
            REP(nc, 2){
                ll dist = INFF; 
                REP(g, 2){
                    if((f[1] & (1 << g))){
                        ll tm = sq(f[0] - nr, nc - g);
                        dist = min(dist, tm); 
                    }
                    if((s[1] & (1 << g))){
                        ll tm = sq(s[0] - nr, nc - g);
                        dist = min(dist, tm);
                    }
                    
                }
                if((dist > res[0]) || (dist == res[0] && nr < res[1]) || (dist == res[0] && nr == res[1] && nc < res[2])){
                    res[0] = dist;
                    res[1] = nr;
                    res[2] = nc;
                }
            }
        }
        return res;
    };
    auto cmp = [&](array<ll, 3> f, array<ll, 3> s){
        if(f[0] == s[0]){
            return tie(f[1], f[2]) < tie(s[1], s[2]);
        }
        else{
            return f[0] > s[0];
        }
    };
    set<array<ll, 3>, decltype(cmp)> pq(cmp);
    pq.insert(get_mid({-1, -1}, {-1, -1}));
    set<array<int, 2>> occupied;
    vector<array<int, 2>> mapka; 
    auto get_next = [&](int row)->array<int, 2>{
        auto it = occupied.lower_bound({row + 1, -1});
        if(it == occupied.end()){
            return {-1, -1};
        }
        else{
            return *it;
        }
    };
    auto get_prev = [&](int row)->array<int, 2>{
        auto it = occupied.lower_bound({row, -1}); 
        if(it == occupied.begin()){
            return {-1, -1};
        }
        else{
            it--;
            return *it;
        } 
    }; 
    REP(i, m){
        char e;
        cin >> e;
        if(e == 'E'){
            auto v = *pq.begin();
            pq.erase(pq.begin());
            auto it = occupied.lower_bound({v[1], 0});
            mapka.pb({v[1], v[2]});
            array<int, 2> tm;
            if(it != occupied.end() && (*it)[0] == v[1]){
                tm = (*it);
                occupied.erase(it);
                tm[1] |= (1 << v[2]);
                occupied.insert(tm);
            }
            else{
                tm = {v[1], (1 << v[2])};
                occupied.insert(tm);
            }
            pq.insert(get_mid(tm, get_next(v[1])));
            pq.insert(get_mid(get_prev(v[1]), tm)); 
            cout << v[1] << " " << v[2] + 1 << "\n";
        }
        else{
            int id;
            cin >> id;
            id--;
            pq.erase(get_mid(mapka[id], get_next(mapka[id][0])));
            pq.erase(get_mid(get_prev(mapka[id][0]), mapka[id]));
            auto it = occupied.lower_bound({mapka[id][0], -1});
            array<int, 2> tm;
            if((*it)[1] == 3){
                tm = (*it);
                occupied.erase(it);
                tm[1] &= (~(1 << mapka[id][1]));
                occupied.insert(tm);
            }
            else{
                tm = {-1, -1};
                occupied.erase(it);
            }
            array<int, 2> nl = {-1, -1};
            int r = mapka[id][0];
            if(tm == nl){
                pq.insert(get_mid(get_prev(r), get_next(r)));
            }
            else{
                pq.insert(get_mid(tm, get_next(r)));
                pq.insert(get_mid(get_prev(r), tm));
            }
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

tram.cpp: In function 'int main()':
tram.cpp:125:53: warning: narrowing conversion of 'v.std::array<long long int, 3>::operator[](1)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  125 |             auto it = occupied.lower_bound({v[1], 0});
      |                                                     ^
tram.cpp:126:34: warning: narrowing conversion of 'v.std::array<long long int, 3>::operator[](1)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  126 |             mapka.pb({v[1], v[2]});
      |                                  ^
tram.cpp:126:34: warning: narrowing conversion of 'v.std::array<long long int, 3>::operator[](2)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
tram.cpp:135:40: warning: narrowing conversion of 'v.std::array<long long int, 3>::operator[](1)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  135 |                 tm = {v[1], (1 << v[2])};
      |                                        ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20