Submission #1273459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273459		anhkhoa	Tram (CEOI13_tram)	C++17	0 / 100	21 ms	12172 KiB

tram

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

struct Seat {int r,c;};
struct Cand {
    long long d2; int r,c;
    bool operator<(const Cand& o) const {
        if (d2!=o.d2) return d2<o.d2;
        if (r!=o.r) return r>o.r;
        return c>o.c;
    }
};

int N,M;
vector<Seat> ans;
vector<bool> isEnter;
vector<vector<bool>> taken;
set<int> occ;
priority_queue<Cand> pq;

long long dist2(int r,int c,const set<int>& occ){
    long long best=LLONG_MAX;
    auto it=occ.lower_bound(r);
    if(it!=occ.end()){
        int rr=*it;
        best=min(best,1LL*(r-rr)*(r-rr)+(c==1? (taken[rr][2]?1:0): (taken[rr][1]?1:0)));
        best=min(best,1LL*(r-rr)*(r-rr)+(c-1)*(c-1)); // check same col
        best=min(best,1LL*(r-rr)*(r-rr)+(c-2)*(c-2));
    }
    if(it!=occ.begin()){
        --it; int rr=*it;
        best=min(best,1LL*(r-rr)*(r-rr)+(c-1)*(c-1));
        best=min(best,1LL*(r-rr)*(r-rr)+(c-2)*(c-2));
    }
    return best;
}

bool valid(const Cand& x){
    if(x.r<1||x.r>N||taken[x.r][x.c]) return false;
    return true;
}

void addCand(int r,int c){
    if(r<1||r>N) return;
    if(taken[r][c]) return;
    long long d=dist2(r,c,occ);
    pq.push({d,r,c});
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N>>M;
    ans.resize(M+1);
    isEnter.resize(M+1);
    taken.assign(N+1,vector<bool>(3,false));

    for(int k=1;k<=M;k++){
        char t; cin>>t;
        if(t=='E'){
            isEnter[k]=true;
            Seat chosen;
            if(occ.empty()){
                chosen={1,1};
            } else {
                while(!pq.empty() && !valid(pq.top())) pq.pop();
                Cand best=pq.top(); pq.pop();
                chosen={best.r,best.c};
            }
            taken[chosen.r][chosen.c]=true;
            ans[k]=chosen;
            cout<<chosen.r<<" "<<chosen.c<<"\n";
            occ.insert(chosen.r);

            // thêm ứng viên mới từ hàng này và lân cận
            addCand(chosen.r,3-chosen.c);
            addCand(chosen.r-1,1); addCand(chosen.r-1,2);
            addCand(chosen.r+1,1); addCand(chosen.r+1,2);
        }else{
            int p; cin>>p;
            Seat s=ans[p];
            taken[s.r][s.c]=false;
            if(!taken[s.r][1] && !taken[s.r][2]) occ.erase(s.r);
            addCand(s.r,1); addCand(s.r,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