oj.uz

Submission #1080171

# Submission time Handle Problem Language Result Execution time Memory
1080171 2024-08-29T07:42:15 Z GrindMachine Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 8840 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 = 2e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

#include "plants.h"

vector<int> id(N);

void init(int k, std::vector<int> a) {
    k--;
    int n = sz(a);
    vector<bool> rem(n);
    int iter = 0;

    while(count(all(rem),0)){
        iter++;

        vector<int> zeros;
        rep(i,n){
            if(rem[i]) conts;
            if(!a[i]){
                zeros.pb(i);
            }
        }

        sort(all(zeros));
        
        if(sz(zeros) == 1){
            trav(i,zeros){
                rem[i] = 1;
                id[i] = iter;
                int j = i-1;
                rep1(x,k){
                    j = (j%n+n)%n;
                    a[j]--;
                    j--;
                }
            }   
        }
        else{
            int pz = zeros.back();
            trav(i,zeros){
                int d = (i-pz+n)%n;
                if(d > k){
                    rem[i] = 1;
                    id[i] = iter;
                    int j = i-1;
                    rep1(x,k){
                        j = (j%n+n)%n;
                        a[j]--;
                        j--;
                    }
                }

                pz = i;
            }
        }
    }
}

int compare_plants(int x, int y) {
    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 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Incorrect 0 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 0 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 10 ms 1116 KB Output is correct
7 Correct 250 ms 5888 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 12 ms 1116 KB Output is correct
10 Correct 245 ms 5756 KB Output is correct
11 Correct 340 ms 5772 KB Output is correct
12 Correct 181 ms 6008 KB Output is correct
13 Correct 310 ms 5992 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 0 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 10 ms 1116 KB Output is correct
7 Correct 250 ms 5888 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 12 ms 1116 KB Output is correct
10 Correct 245 ms 5756 KB Output is correct
11 Correct 340 ms 5772 KB Output is correct
12 Correct 181 ms 6008 KB Output is correct
13 Correct 310 ms 5992 KB Output is correct
14 Correct 2904 ms 6224 KB Output is correct
15 Execution timed out 4045 ms 8792 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 47 ms 5688 KB Output is correct
4 Execution timed out 4032 ms 8840 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 0 ms 1116 KB Output is correct
3 Incorrect 1 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Incorrect 0 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Incorrect 0 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -