結果

問題 No.953 席
コンテスト
ユーザー tarattata1
提出日時 2019-12-16 01:47:10
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 5,656 bytes
コンパイル時間 929 ms
コンパイル使用メモリ 90,712 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2024-07-02 18:50:25
合計ジャッジ時間 6,943 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’:
main.cpp:38:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |     scanf("%d%d%d%d", &n, &K1, &K2, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:60:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |         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;

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() || !ss.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);
            }
        }
        
        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