oj.uz

Submission #1080312

# Submission time Handle Problem Language Result Execution time Memory
1080312 2024-08-29T08:47:26 Z GrindMachine Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 113520 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; ++i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
    x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
    x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
    return "'"+s+"'";
}

string to_string(const char* s){
    return to_string((string)s);
}

string to_string(bool b){
    return b?"true":"false";
}

template<typename A>
string to_string(A v){
    string res = "{";
    trav(x,v){
        res += to_string(x)+",";
    }
    if(res.back() == ',') res.pop_back();
    res += "}";
    return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
    return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1<<15;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

#include "plants.h"

pii d_neutral = {inf1,-1};
vector<pii> tr(4*N,d_neutral);
vector<int> lz(4*N);

void propagate(int x, int lx, int rx){
    int v = lz[x];
    tr[x].ff += v;

    if(rx-lx > 1){
        lz[x<<1] += v;
        lz[x<<1|1] += v;
    }

    lz[x] = 0;
}

void rupd(int x, int lx, int rx, int l, int r, int v){
    propagate(x,lx,rx);

    if(lx >= r or rx <= l) return;
    if(lx >= l and rx <= r){
        lz[x] = v;
        propagate(x,lx,rx);
        return;
    }

    int mid = (lx+rx)>>1;
    rupd(x<<1,lx,mid,l,r,v);
    rupd(x<<1|1,mid,rx,l,r,v);

    tr[x] = min(tr[x<<1],tr[x<<1|1]);
}

void rupd(int l, int r, int v){
    rupd(1,0,N,l,r+1,v);
}

pii query(){
    propagate(1,0,N);
    return tr[1];
}

void build(int x, int lx, int rx, vector<int> &a){
    if(rx-lx == 1){
        if(lx < sz(a)){
            tr[x] = {a[lx],lx};
        }
        return;
    }

    int mid = (lx+rx) >> 1;
    build(x<<1,lx,mid,a);
    build(x<<1|1,mid,rx,a);
    tr[x] = min(tr[x<<1],tr[x<<1|1]);
}

void build(vector<int> &a){
    build(1,0,N,a);
}

vector<int> id(N);
vector<int> adj[N];
bool reach[N][N];

void dfs(int u, int s){
    reach[s][u] = 1;
    trav(v,adj[u]){
        if(reach[s][v]) conts;
        dfs(v,s);
    }
}

void init(int k, std::vector<int> a) {
    k--;
    int n = sz(a);
    build(a);

    int iter = 0;
    int rem_cnt = 0;
    vector<bool> remm(n);

    auto rem = [&](int i){
        remm[i] = 1;
        rem_cnt++;
        id[i] = iter;
        if(i-k >= 0){
            rupd(i-k,i-1,-1);
        }
        else{
            rupd(0,i-1,-1);
            rupd(i-k+n,n-1,-1);
        }

        // int j = i;
        // rep1(x,k){
        //     j = (j+1)%n;
        //     if(!remm[j]){
        //         adj[i].pb(j);
        //     }
        //     else{
        //         adj[j].pb(i);
        //     }
        // }
    };

    set<int> zeros;
    set<pii> dis;

    while(rem_cnt < n){
        iter++;

        while(true){
            auto [mn,i] = query();
            if(mn == 0){
                rupd(i,i,inf1);

                zeros.insert(i);
                auto it = zeros.find(i);
                int prevv = -1, nxt = -1;
                if(it != zeros.begin()){
                    prevv = *prev(it);
                }
                if(next(it) != zeros.end()){
                    nxt = *next(it);
                }

                if(prevv != -1 and nxt != -1) dis.erase({nxt-prevv,nxt});
                if(prevv != -1) dis.insert({i-prevv,i});
                if(nxt != -1) dis.insert({nxt-i,nxt});
            }
            else{
                break;
            }
        }

        if(sz(zeros) == 1){
            trav(i,zeros){
                rem(i);
            }

            zeros.clear();
            dis.clear();
            conts;
        }

        vector<int> del;

        {
            int i = *zeros.begin(), j = *zeros.rbegin();
            int d = (i-j+n)%n;
            if(d > k){
                del.pb(i);
            }            
        }

        for(auto it = dis.rbegin(); it != dis.rend(); ++it){
            auto [d,i] = *it;
            if(d > k){
                del.pb(i);
            }
            else{
                break;
            }
        }

        trav(i,del){
            rem(i);

            auto it = zeros.find(i);
            int prevv = -1, nxt = -1;
            if(it != zeros.begin()){
                prevv = *prev(it);
            }
            if(next(it) != zeros.end()){
                nxt = *next(it);
            }

            zeros.erase(it);

            if(prevv != -1) dis.erase({i-prevv,i});
            if(nxt != -1) dis.erase({nxt-i,nxt});
            if(prevv != -1 and nxt != -1) dis.insert({nxt-prevv,nxt});
        }
    }

    rep(i,n){
        int j = i;
        rep1(x,k){
            j = (j+1)%n;
            if(id[i] < id[j]){
                adj[i].pb(j);
            }
            else{
                adj[j].pb(i);
            }
        }
    }

    rep(i,n){
        dfs(i,i);
    }
}

int compare_plants(int x, int y) {
    if(reach[x][y]) return 1;
    if(reach[y][x]) return -1;
    return 0;

    if(id[x] < id[y]) return 1;
    if(id[x] > id[y]) return -1;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2900 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 42 ms 5768 KB Output is correct
7 Correct 106 ms 89172 KB Output is correct
8 Runtime error 92 ms 8276 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 335 ms 12152 KB Output is correct
7 Execution timed out 4040 ms 113520 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 335 ms 12152 KB Output is correct
7 Execution timed out 4040 ms 113520 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 57 ms 13776 KB Output is correct
4 Runtime error 68 ms 7824 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 3 ms 3164 KB Output is correct
7 Correct 10 ms 4700 KB Output is correct
8 Correct 14 ms 5208 KB Output is correct
9 Correct 10 ms 4700 KB Output is correct
10 Correct 14 ms 4700 KB Output is correct
11 Correct 10 ms 4700 KB Output is correct
12 Correct 11 ms 4700 KB Output is correct
13 Correct 22 ms 5264 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 49 ms 7496 KB Output is correct
6 Runtime error 82 ms 6736 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2900 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 42 ms 5768 KB Output is correct
7 Correct 106 ms 89172 KB Output is correct
8 Runtime error 92 ms 8276 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -