oj.uz

Submission #1062660

# Submission time Handle Problem Language Result Execution time Memory
1062660 2024-08-17T09:39:01 Z ewirlan Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 9296 KB 
//
#ifndef __SIZEOF_INT128__
    #define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
    string name{""};
    time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
    duration<float, std::milli> dur;
    Timer() = default;
    Timer(string nm): name(nm) {}
    ~Timer() {
        end = high_resolution_clock::now(); dur= end - start;
        cout << "@" << name << "> " << dur.count() << " ms" << '\n';
    }
};
template <typename T = int> inline T in()
{
    static T x;
    std::cin >> x;
    return x;
}
std::string yn(bool b)
{
    if(b) return "YES\n";
    else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
    for(const auto& i : wek)out << i << ' ';
    return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
    out << '{'<<par.first<<", "<<par.second<<"}";
    return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
#include "plants.h"
constexpr int maxn = 2e5 + 3;
int ls[maxn], rs[maxn], ko[maxn];
int ld[maxn], rd[maxn];
int n;
void init(int k, vector <int> r)
{
    n = sz(r);
    ko[n] = -1;
    rep(c, 1, n+1){
        int a(-1);
        rep(i, 0, n)if(r[i] == 0){
            bool b(1);
            rep(j, 1, k)b &= !!r[(n+i-j)%n];
            if(b){
                a = i;
                break;
            }
        }
        rep(j, 1, k)if(r[(n+a-j)%n] > 0) r[(n+a-j)%n]--;
    
        int m(0), g(n), gd{-1};
        rep(j, 1, k)if(r[(n+a-j)%n] < m){
            m = r[(n+a-j)%n];
            g = (n+a-j)%n;
            gd = j;
        }
        ls[a] = g;
        ld[a] = gd;
        m = 0;
        g = n;
        gd = -1;
        rep(j, 1, k)if(r[(a+j)%n] < m){
            m = r[(a+j)%n];
            g = (a+j)%n;
            gd = j;
        }
        rs[a] = g;
        rd[a] = gd;

        r[a] = -c;
        ko[a] = c;
    }
}
int compare_plants(int x, int y)
{
    int m(1);
    if(ko[x] > ko[y]){
        swap(x, y);
        m = -1;
    }
    // cerr << "comp(" << x << ", " << y << ")\n";
    int z(y);
    ll d(0);
    // cerr << ko[x] << ' ' << ko[y] << ' ' << ko[ls[y]] << '\n';
    while(ko[ls[z]] >= ko[x]){
        // cerr << z << " -> " << ls[z] << '\n';
        d += ld[z];
        z = ls[z];
    }
    // cerr << 'L' << d << '\n';
    if(x < y){
        if(y-d <= x)return m;
    }
    else{
        if(y-d <= x-n)return m;
    }
    // cerr << "reset\n";
    z = y;
    d = 0;
    while(ko[rs[z]] >= ko[x]){
        // cerr << z << " -> " << rs[z] << '\n';
        d += rd[z];
        z = rs[z];
    }
    // cerr << 'R' << d << '\n';
    if(x < y){
        if(y+d >= x+n)return m;
    }
    else{
        if(y+d >= x)return m;
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 33 ms 4076 KB Output is correct
7 Correct 217 ms 7780 KB Output is correct
8 Execution timed out 4032 ms 9296 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 11 ms 348 KB Output is correct
7 Correct 1227 ms 7252 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 12 ms 2532 KB Output is correct
10 Correct 1203 ms 5208 KB Output is correct
11 Correct 877 ms 5200 KB Output is correct
12 Correct 497 ms 7248 KB Output is correct
13 Correct 1484 ms 5096 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 11 ms 348 KB Output is correct
7 Correct 1227 ms 7252 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 12 ms 2532 KB Output is correct
10 Correct 1203 ms 5208 KB Output is correct
11 Correct 877 ms 5200 KB Output is correct
12 Correct 497 ms 7248 KB Output is correct
13 Correct 1484 ms 5096 KB Output is correct
14 Execution timed out 4056 ms 5468 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 167 ms 6996 KB Output is correct
4 Execution timed out 4005 ms 7736 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 10 ms 3364 KB Output is correct
8 Correct 14 ms 3420 KB Output is correct
9 Correct 13 ms 1372 KB Output is correct
10 Correct 13 ms 1372 KB Output is correct
11 Correct 10 ms 1372 KB Output is correct
12 Correct 10 ms 1372 KB Output is correct
13 Correct 19 ms 1360 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2496 KB Output is correct
5 Correct 3 ms 2532 KB Output is correct
6 Execution timed out 4094 ms 8260 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 33 ms 4076 KB Output is correct
7 Correct 217 ms 7780 KB Output is correct
8 Execution timed out 4032 ms 9296 KB Time limit exceeded
9 Halted 0 ms 0 KB -