結果

問題 No.953 席
ユーザー tarattata1tarattata1
提出日時 2019-12-16 10:23:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 254 ms / 2,000 ms
コード長 4,926 bytes
コンパイル時間 799 ms
コンパイル使用メモリ 94,692 KB
実行使用メモリ 13,624 KB
最終ジャッジ日時 2023-09-15 17:24:21
合計ジャッジ時間 7,286 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 155 ms
11,132 KB
testcase_03 AC 144 ms
11,132 KB
testcase_04 AC 150 ms
11,080 KB
testcase_05 AC 127 ms
10,860 KB
testcase_06 AC 156 ms
11,132 KB
testcase_07 AC 209 ms
12,072 KB
testcase_08 AC 254 ms
13,056 KB
testcase_09 AC 172 ms
11,864 KB
testcase_10 AC 55 ms
5,816 KB
testcase_11 AC 175 ms
10,452 KB
testcase_12 AC 223 ms
12,668 KB
testcase_13 AC 253 ms
13,520 KB
testcase_14 AC 206 ms
12,400 KB
testcase_15 AC 197 ms
12,140 KB
testcase_16 AC 202 ms
12,408 KB
testcase_17 AC 169 ms
12,732 KB
testcase_18 AC 166 ms
12,460 KB
testcase_19 AC 195 ms
13,256 KB
testcase_20 AC 167 ms
12,404 KB
testcase_21 AC 145 ms
11,340 KB
testcase_22 AC 224 ms
12,728 KB
testcase_23 AC 178 ms
11,720 KB
testcase_24 AC 184 ms
11,664 KB
testcase_25 AC 253 ms
13,624 KB
testcase_26 AC 112 ms
10,864 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;
using namespace std;

int n;                   // seatの数
int Q;                   // 人の数
vector<ll> a,b;          // input

vector<int> vv;          // vv[i]：i番目の優先順位番号の席のID(0<=i<n)
vector<int> vv2;         // vvの逆変換

set<pair<ll,pair<int,int> > > z;         // time,flag(1:add, 0:del),id

set<int> s0;             // ptが0の席の優先順位番号
set<int> s1;             // ptが1,2の席の優先順位番号
vector<int> pt;          // pt[i]：優先順位番号iの席のpoint：その席に座っている人がいたら+10、隣りに座っている人がいたら+1
vector<int> status;      // 各人が座った席の優先順位番号(>=0)  -1なら待機中
set<int> ss;             // 待機中の人のid

void update(int q, int q_pt)   // 優先順位番号qの席のポイントがq_ptになったときのs0,s1の更新
{
    if(q_pt==0) s0.insert(q);
    else s0.erase(q);

    if(q_pt==1 || q_pt==2) s1.insert(q);
    else s1.erase(q);
}

void seat(int id, int q, ll tt)     // idの人が優先順位番号qの席に時刻ttに座る
{
    status[id]=q;
    pt[q]+=10;
    update(q,pt[q]);
    if(vv[q]>0) {
        int tmp=vv2[vv[q]-1];
        pt[tmp]++;
        update(tmp,pt[tmp]);
    }
    if(vv[q]<n-1) {
        int tmp=vv2[vv[q]+1];
        pt[tmp]++;
        update(tmp,pt[tmp]);
    }
    z.insert(make_pair(tt+b[id],make_pair(0,id)));
}

void unseat(int id, int q)
{
    pt[q]-=10;
    update(q,pt[q]);
    if(vv[q]>0) {
        int tmp=vv2[vv[q]-1];
        pt[tmp]--;
        update(tmp,pt[tmp]);
    }
    if(vv[q]<n-1) {
        int tmp=vv2[vv[q]+1];
        pt[tmp]--;
        update(tmp,pt[tmp]);
    }
}

int main(int argc, char* argv[])
{
    int K1,K2;
    scanf("%d%d%d%d", &n, &K1, &K2, &Q);
    assert(abs(K1-K2)==1);
    K1--; K2--;

    // prepare vv
    int i;
    {
        int diff=K2-K1;
        for(i=0; i<n; i++) {
            int tmp=K1-diff*i;
            if(tmp>=0 && tmp<n) vv.push_back(tmp);
            tmp=K2+diff*i;
            if(tmp>=0 && tmp<n) vv.push_back(tmp);
        }
    }

    // prepare vv2
    vv2.resize(n);
    for(i=0; i<n; i++) {
        vv2[vv[i]]=i;
    }

    // prepare z
    a.resize(Q);
    b.resize(Q);
    for(i=0; i<Q; i++) {
        scanf("%lld%lld", &a[i], &b[i]);
        z.insert(make_pair(a[i],make_pair(1,i)));
    }

    // prepare
    pt.resize(n);     
    status.resize(Q); 
    for(i=0; i<n; i++) {
        s0.insert(i);
    }

    // simulation
    ll tt_prev=-INF;
    int flag_prev=-INF;
    while(!z.empty()) {
        auto it0=z.begin();
        ll  tt=it0->first;
        int flag=it0->second.first;
        int id=it0->second.second;

        if(tt_prev!=tt || flag_prev!=flag) {
            if(!ss.empty() && !s0.empty()) {
                int id=(*ss.begin());
                ss.erase(id);
                int q=(*s0.begin());
                s0.erase(q);
                seat(id,q,tt_prev);
                continue;
            }

            if(!ss.empty() && !s1.empty()) {
                int id=(*ss.begin());
                ss.erase(id);
                int q=(*s1.begin());
                s1.erase(q);
                seat(id,q,tt_prev);
                continue;
            }
        }
        z.erase(*it0);

        if(flag==1) {
            if(!s0.empty()) {
                int q=(*s0.begin());
                seat(id,q,tt);
            }
            else if(!s1.empty()) {
                int q=(*s1.begin());
                seat(id,q,tt);
            }
            else {
                status[id]=-1;
                ss.insert(id);
            }
        }
        else {
            assert(status[id]>=0);
            int q=status[id];
            unseat(id,q);
        }

        if(z.empty()) {
            while(!ss.empty() && !s0.empty()) {
                int id=(*ss.begin());
                ss.erase(id);
                int q=(*s0.begin());
                s0.erase(q);
                seat(id,q,tt);
            }

            while(!ss.empty() && !s1.empty()) {
                int id=(*ss.begin());
                ss.erase(id);
                int q=(*s1.begin());
                s1.erase(q);
                seat(id,q,tt);
            }
        }
        
        tt_prev=tt;
        flag_prev=flag;
    }

    for(i=0; i<Q; i++) {
        assert(status[i]>=0);
        printf("%d\n", vv[status[i]]+1);
    }

    return 0;
}
0