제출 #1311552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311552		Zbyszek99	Seesaw (JOI22_seesaw)	C++20	100 / 100	201 ms	32908 KiB

seesaw

#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 rand(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;

struct matrix
{
    bool mat[2][2];
    matrix()
    {
        rep(i,2) rep(j,2) mat[i][j] = 0;
    }
    matrix operator+(const matrix& d)
    {
        matrix res;
        if(mat[0][0] && d.mat[0][0]) res.mat[0][0] = 1;
        if(mat[0][1] && d.mat[1][0]) res.mat[0][0] = 1;

        if(mat[0][0] && d.mat[0][1]) res.mat[0][1] = 1;
        if(mat[0][1] && d.mat[1][1]) res.mat[0][1] = 1;
        
        if(mat[1][0] && d.mat[0][0]) res.mat[1][0] = 1;
        if(mat[1][1] && d.mat[1][0]) res.mat[1][0] = 1;
        
        if(mat[1][0] && d.mat[0][1]) res.mat[1][1] = 1;
        if(mat[1][1] && d.mat[1][1]) res.mat[1][1] = 1;
        return res;
    }
};

const int tree_siz = 1024*512-1;
matrix drzewo[tree_siz];

bool is_way()
{
    rep(i,2)
    {
        rep(j,2)
        {
            if(drzewo[0].mat[i][j]) return true;
        }
    }
    return false;
}

void upd(int v)
{
    drzewo[v-1] = drzewo[v*2-1] + drzewo[v*2];
    if(v != 1) upd(v/2);
}

pii edges[200'001][2];
bool used[200'001][2];
ld val[200'001][2];
matrix mat[200'001];

void upd_poz(int ind)
{
    rep(d1,2) rep(d2,2) mat[ind].mat[d1][d2] = 0;
    if(used[ind][0] && edges[ind][0].ff) mat[ind].mat[0][0] = 1;
    if(used[ind][0] && edges[ind][0].ss) mat[ind].mat[0][1] = 1;
    if(used[ind][1] && edges[ind][1].ff) mat[ind].mat[1][0] = 1;
    if(used[ind][1] && edges[ind][1].ss) mat[ind].mat[1][1] = 1;
    drzewo[tree_siz/2+ind] = mat[ind];
    upd((tree_siz/2+ind+1)/2);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    rep(i,tree_siz)
    {
        rep(d1,2) rep(d2,2) drzewo[i].mat[d1][d2] = 1;
    }
    int n;
    cin >> n;
    vector<ld> v(n+1);
    ld sum = 0;
    rep(i,n)
    {
        cin >> v[i+1];
        sum += v[i+1];
    }
    ld start_mid = sum / (ld)n;
    ld pop1 = sum;
    pii seg1 = {1,n};
    ld pop2 = -1;
    pii seg2 = {-1,-1};
    val[0][0] = sum/(ld)n;
    val[0][1] = -1e9;
    rep2(i,1,n-1)
    {
        if(pop2 == -1)
        {
            val[i][0] = (sum-v[n]) / (ld)(n-1);
            val[i][1] = (sum-v[1]) / (ld)(n-1);
            edges[i-1][0] = {1,1};
            edges[i-1][1] = {0,0};
            pop1 = sum-v[n];
            pop2 = sum-v[1];
            seg1 = {1,n-1};
            seg2 = {2,n};
            edges[i][0] = {1,1};
            edges[i][1] = {1,1}; 
          //  cout << pop1 << " " << pop2 << "\n" << seg1.ff << " " << seg1.ss << "\n" << seg2.ff << " " << seg2.ss << " seg\n\n";
            continue;
        }
        pair<ld,pii> next_L = {-1e16+1,{-1,-1}};
        pair<ld,pii> next_R = {+1e16-1,{-1,-1}};
        //L
        if((pop1 - v[seg1.ss]) / (ld)(n-i) <= start_mid)
        {
            next_L = max(next_L, {(pop1 - v[seg1.ss]),{seg1.ff,seg1.ss-1}});
        }
        if((pop2 - v[seg2.ss]) / (ld)(n-i) <= start_mid)
        {
            next_L = max(next_L, {(pop2 - v[seg2.ss]),{seg2.ff,seg2.ss-1}});
        }
        //R
        if((pop1 - v[seg1.ff]) / (ld)(n-i) >= start_mid)
        {
            next_R = min(next_R, {(pop1 - v[seg1.ff]),{seg1.ff+1,seg1.ss}});
        }
        if((pop2 - v[seg2.ff]) / (ld)(n-i) >= start_mid)
        {
            next_R = min(next_R, {(pop2 - v[seg2.ff]),{seg2.ff+1,seg2.ss}});
        }
        edges[i-1][0] = {0,0};
        edges[i-1][1] = {0,0};
        // 0 0
        if(seg1.ff == next_L.ss.ff && seg1.ss-1 == next_L.ss.ss)
        {
            edges[i-1][0].ff = 1;
        }
        if(seg1.ff+1 == next_L.ss.ff && seg1.ss == next_L.ss.ss)
        {
            edges[i-1][0].ff = 1;
        }
        // 0 1
        if(seg1.ff + 1 == next_R.ss.ff && seg1.ss == next_R.ss.ss)
        {
            edges[i-1][0].ss = 1;
        }
        if(seg1.ff == next_R.ss.ff && seg1.ss -1 == next_R.ss.ss)
        {
            edges[i-1][0].ss = 1;
        }
        // 1 0
        if(seg2.ff == next_L.ss.ff && seg2.ss-1 == next_L.ss.ss)
        {
            edges[i-1][1].ff = 1;
        }
        if(seg2.ff+1 == next_L.ss.ff && seg2.ss == next_L.ss.ss)
        {
            edges[i-1][1].ff = 1;
        }
        // 1 1
        if(seg2.ff + 1 == next_R.ss.ff && seg2.ss == next_R.ss.ss)
        {
            edges[i-1][1].ss = 1;
        }
        if(seg2.ff == next_R.ss.ff && seg2.ss -1 == next_R.ss.ss)
        {
            edges[i-1][1].ss = 1;
        }
        val[i][0] = next_L.ff / (ld)(n-i);
        val[i][1] = next_R.ff / (ld)(n-i);
        pop1 = next_L.ff;
        pop2 = next_R.ff;
        seg1 = next_L.ss;
        seg2 = next_R.ss;

        edges[i][0] = {1,1};
        edges[i][1] = {1,1}; 
       // cout << pop1 << " " << pop2 << "\n" << seg1.ff << " " << seg1.ss << "\n" << seg2.ff << " " << seg2.ss << " seg\n\n";
    }
    vector<pair<ld,pii>> points;
    rep(i,n)
    {
        points.pb({val[i][0],{i,0}});
        if(i != 0)
        {
            points.pb({val[i][1],{i,1}});
        }
        upd_poz(i);
    }
    sort(all(points));
    ld ans = 1e16;
    int p = 0;
    int k = 0;
    while(p < siz(points))
    {
        if(p != 0)
        {
            used[points[p-1].ss.ff][points[p-1].ss.ss] = 0;
            upd_poz(points[p-1].ss.ff);
        }
        used[points[p].ss.ff][points[p].ss.ss] = 1;
        upd_poz(points[p].ss.ff);
        while(!is_way() && k+1 < siz(points))
        {
            k++;
            used[points[k].ss.ff][points[k].ss.ss] = 1;
            upd_poz(points[k].ss.ff);
        }
       // cout << p << " " << k << " " << is_way() << " two\n";
        if(is_way())
        {
            ans = min(ans,points[k].ff-points[p].ff);
        }
        else break;
        p++;
    }
    cout << setprecision(10) << ans << "\n";
}

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33