結果

問題 No.953 席
ユーザー tarattata1tarattata1
提出日時 2019-12-16 02:04:53
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 7,016 bytes
コンパイル時間 934 ms
コンパイル使用メモリ 95,352 KB
実行使用メモリ 12,796 KB
最終ジャッジ日時 2023-09-15 16:24:14
合計ジャッジ時間 6,983 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 204 ms
11,876 KB
testcase_08 AC 255 ms
12,528 KB
testcase_09 AC 173 ms
11,280 KB
testcase_10 AC 53 ms
5,892 KB
testcase_11 AC 179 ms
9,876 KB
testcase_12 WA -
testcase_13 AC 251 ms
12,796 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 194 ms
12,476 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 261 ms
12,760 KB
testcase_26 AC 110 ms
10,016 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;

void update(set<int>& s0, set<int>& s1, int q, int pt)
{
    if(pt==0) s0.insert(q);
    else s0.erase(q);

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

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

    int i;
    vector<int> vv;       // vv[i]：i番目の優先順位番号の席のID(0<=i<n)
    {
        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);
        }
    }
    vector<int> vv2(n);      // vvの逆変換
    for(i=0; i<n; i++) {
        vv2[vv[i]]=i;
    }

    set<pair<int,pair<int,int> > > z;  // time,flag(1:add, 0:del),id
    vector<int> a(Q),b(Q);
    for(i=0; i<Q; i++) {
        scanf("%d%d", &a[i], &b[i]);
        z.insert(make_pair(a[i],make_pair(1,i)));
    }

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

    for(i=0; i<n; i++) {
        s0.insert(i);
    }

    int tt_prev=-INF;
    int flag_prev=-INF;
    while(!z.empty()) {
        auto it0=z.begin();
        int 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());
                status[id]=q;
                pt[q]+=10;
                update(s0,s1,q,pt[q]);
                if(vv[q]>0) {
                    int tmp=vv2[vv[q]-1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                if(vv[q]<n-1) {
                    int tmp=vv2[vv[q]+1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                z.insert(make_pair(tt_prev+b[id],make_pair(0,id)));
            }

            while(!ss.empty() && !s1.empty()) {
                int id=(*ss.begin());
                ss.erase(id);

                int q=(*s1.begin());
                status[id]=q;
                pt[q]+=10;
                update(s0,s1,q,pt[q]);
                if(vv[q]>0) {
                    int tmp=vv2[vv[q]-1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                if(vv[q]<n-1) {
                    int tmp=vv2[vv[q]+1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                z.insert(make_pair(tt_prev+b[id],make_pair(0,id)));
            }
        }

        if(flag==1) {
            if(!s0.empty()) {
                int q=(*s0.begin());
                status[id]=q;
                pt[q]+=10;
                update(s0,s1,q,pt[q]);
                if(vv[q]>0) {
                    int tmp=vv2[vv[q]-1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                if(vv[q]<n-1) {
                    int tmp=vv2[vv[q]+1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                z.insert(make_pair(tt+b[id],make_pair(0,id)));
            }
            else if(!s1.empty()) {
                int q=(*s1.begin());
                status[id]=q;
                pt[q]+=10;
                update(s0,s1,q,pt[q]);
                if(vv[q]>0) {
                    int tmp=vv2[vv[q]-1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                if(vv[q]<n-1) {
                    int tmp=vv2[vv[q]+1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                z.insert(make_pair(tt+b[id],make_pair(0,id)));
            }
            else {
                status[id]=-1;
                ss.insert(id);
            }
        }
        else {
            if(status[id]>=0) {
                int q=status[id];
                pt[q]-=10;
                update(s0,s1,q,pt[q]);
                if(vv[q]>0) {
                    int tmp=vv2[vv[q]-1];
                    pt[tmp]--;
                    update(s0,s1,tmp,pt[tmp]);
                }
                if(vv[q]<n-1) {
                    int tmp=vv2[vv[q]+1];
                    pt[tmp]--;
                    update(s0,s1,tmp,pt[tmp]);
                }
            }
            else {
                ss.erase(id);
            }
        }

        if(z.empty()) {
            while(!ss.empty() && !s0.empty()) {
                int id=(*ss.begin());
                ss.erase(id);

                int q=(*s0.begin());
                status[id]=q;
                pt[q]+=10;
                update(s0,s1,q,pt[q]);
                if(vv[q]>0) {
                    int tmp=vv2[vv[q]-1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                if(vv[q]<n-1) {
                    int tmp=vv2[vv[q]+1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                z.insert(make_pair(tt_prev+b[id],make_pair(0,id)));
            }

            while(!ss.empty() && !s1.empty()) {
                int id=(*ss.begin());
                ss.erase(id);

                int q=(*s1.begin());
                status[id]=q;
                pt[q]+=10;
                update(s0,s1,q,pt[q]);
                if(vv[q]>0) {
                    int tmp=vv2[vv[q]-1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                if(vv[q]<n-1) {
                    int tmp=vv2[vv[q]+1];
                    pt[tmp]++;
                    update(s0,s1,tmp,pt[tmp]);
                }
                z.insert(make_pair(tt_prev+b[id],make_pair(0,id)));
            }
        }
        
        tt_prev=tt;
        flag_prev=flag;
    }

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

    return 0;
}
0