题解：P15215 [NWERC 2025] Juggling Keys

zjd2013 · 2026-03-08 17:24:11 · 题解

link

Solution

只有在公寓里没人时才要钥匙，而最多只有 10^5 次旅行，不多，可以直接模拟过程，第一次模拟是否需要钥匙，第二次模拟是否用太多钥匙，如果钥匙数在某一刻变成了负的，那就不行了。

Code

:::success[code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef double db;
typedef __int128 i128;
const ll inf=9e18,maxn=1e5+1;
const i128 Inf=1e35;
ll n,k,q;
struct node
{
    ll t,num;
    bool fl;
    bool operator<(node a) const
    {
        return t<a.t;
    }
};
ch s[maxn];
vector<node> vec;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>q;
    for(int i=1;i<=q;i++)
    {
        ll p,l,r;
        cin>>p>>l>>r;
        vec.push_back({l,i,0});
        vec.push_back({r,i,1});
    }
    sort(vec.begin(),vec.end());
    for(int i=1;i<=q;i++) s[i]='0';
    ll cnt=n;
    for(node v:vec)
    {
        if(v.fl)
        {
            if(cnt==0) s[v.num]='1';
            cnt++;
        }
        else cnt--;
    }
    cnt=k;
    for(node v:vec)
    {
        if(v.fl)
        {
            if(s[v.num]=='1') cnt++;
        }
        else
        {
            if(s[v.num]=='1') cnt--;
            if(cnt<0) break;
        }
    }
    if(cnt<0) cout<<"impossible";
    else
    {
        for(int i=1;i<=q;i++) cout<<s[i];
    }
}

:::