結果

問題 No.953 席
ユーザー tarattata1tarattata1
提出日時 2019-12-16 10:10:46
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,880 bytes
コンパイル時間 1,643 ms
コンパイル使用メモリ 95,068 KB
実行使用メモリ 13,592 KB
最終ジャッジ日時 2023-09-15 17:20:50
合計ジャッジ時間 8,442 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 219 ms
12,124 KB
testcase_08 AC 284 ms
13,052 KB
testcase_09 AC 191 ms
11,868 KB
testcase_10 AC 58 ms
5,860 KB
testcase_11 AC 199 ms
10,460 KB
testcase_12 WA -
testcase_13 AC 285 ms
13,532 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 171 ms
12,656 KB
testcase_18 AC 167 ms
12,400 KB
testcase_19 AC 198 ms
13,252 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 267 ms
12,796 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 280 ms
13,592 KB
testcase_26 AC 111 ms
10,904 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;
        z.erase(*it0);

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

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

        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