제출 #1136337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136337		Zbyszek99	Sprinklers (CEOI24_sprinklers)	C++20	6 / 100	363 ms	3700 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vl spri;
vl flow;
pii dp[100'001][2];

int next_flow(ll poz)
{
    int p = 0;
    int k = siz(flow)-1;
    int ans = siz(flow);
    while(p <= k)
    {
        int mid = (p+k)/2;
        if(flow[mid] > poz)
        {
            ans = mid;
            k = mid-1;
        }
        else
        {
            p = mid+1;
        }
    }
    return ans;
}

bool solve(ll k)
{
    int n = siz(spri)-1;
    int m = siz(flow);
    rep2(i,1,n)
    {
        dp[i][0] = {-1,-1};
        dp[i][1] = {-1,-1};
    }
    rep2(i,1,n)
    {
        dp[i][0] = {0,-1};
        dp[i][1] = {0,-1};
        // left left
        if(spri[i] - flow[dp[i-1][0].ff] <= k)
        {
            dp[i][0] = max(dp[i][0],{next_flow(spri[i]),0});
        }
        // left right
        if(spri[i] - flow[dp[i-1][1].ff] <= k && i != 1)
        {
            dp[i][0] = max(dp[i][0],{next_flow(max(spri[i],spri[i-1]+k)),1});
        }
        // right left
        if(flow[dp[i-1][0].ff] >= spri[i])
        {
            dp[i][1] = max(dp[i][1],{next_flow(spri[i]+k),0});
        }
        else
        {
            dp[i][1] = max(dp[i][1],{dp[i-1][0].ff,0});
        }
        //right right
        if(flow[dp[i-1][1].ff] >= spri[i])
        {
            dp[i][1] = max(dp[i][1],{next_flow(spri[i]+k),1});
        }
        else
        {
            dp[i][1] = max(dp[i][1],{dp[i-1][1].ff,1});
        }
       // cout << dp[i][0] << " " << dp[i][1] << " " << i << " " << n << " " << m << " dp\n";
        if(dp[i][0].ff == m) return true;
        if(dp[i][1].ff == m) return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    spri.pb(-1);
    int n,m;
    cin >> n >> m;
    rep(i,n)
    {
        int x;
        cin >> x;
        spri.pb(x);
    }
    rep(i,m)
    {
        int x;
        cin >> x;
        flow.pb(x);
    }
    int p = 0;
    int k = 1e9;
    int ans = -1;
    while(p <= k)
    {
        int mid = (p+k)/2;
        if(solve(mid))
        {
            ans = mid;
            k = mid-1;
        }
        else
        {
            p = mid+1;
        }
    }
    cout << ans << "\n";
    if(ans == -1) return 0;
    vector<bool> vans(n,0);
    int cur_done = m;
    solve(ans);
   // cout << next_flow(10) << " nxt\n";
   // rep2(i,1,n)
   // {
   //     cout << dp[i][0].ff << " " << dp[i][1].ff << "\n";
   // }
    int cur_ = 0;
    for(int i = n; i >= 1; i--)
    {
        if(dp[i][0].ff == -1) continue;
        if(dp[i][0].ff == m)
        {
            cur_ = dp[i][0].ss;
            continue;
        }
        else if(dp[i][1].ff == m)
        {
            cur_ = dp[i][1].ss;
            vans[i] = 1;
            continue;
        }
        vans[i] = cur_;
        cur_ = dp[i][cur_].ss;
    }
    rep(i,n)
    {
        if(vans[i] == 0) cout << "L";
        else cout << "R";
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47