結果

問題 No.953 席
コンテスト
ユーザー tarattata1
提出日時 2019-12-16 09:41:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,426 bytes
コンパイル時間 751 ms
コンパイル使用メモリ 89,688 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2024-07-02 19:23:43
合計ジャッジ時間 5,948 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’:
main.cpp:87:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |     scanf("%d%d%d%d", &n, &K1, &K2, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:112:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  112 |         scanf("%d%d", &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

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<int> a,b;         // input

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

set<pair<int,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, int 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);
    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("%d%d", &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
    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());
                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);
        }
        
        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