Submission #334146

#	Time	Username	Problem	Language	Result	Execution time	Memory
334146		balbit	Comparing Plants (IOI20_plants)	C++14	14 / 100	396 ms	8684 KiB

plants

#include <bits/stdc++.h>
#ifndef BALBIT
#include "plants.h"

#endif // BALBIT
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x.size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define bug(...)
#define endl '\n'
#endif // BALBIT

#define REP(i,n) for (int i = 0; i<n;++i)
#define REP1(i,n) for (int i = 1; i<=n;++i)

const int maxn = 5005;
int group[maxn];
int R[maxn];
bool added[maxn];
int n;

inline int F(int x) {
    return x >=n ? x-n: (x<0?x+n:x);
}

void init(int k, vector<int> r) {
    n = SZ(r);
    REP(i,n) R[i] = r[i];
//    REP(i,n) {
//        if (r[i] == 0)
//            for (int j = 1; j<k; ++j) {
//                R[F(i+j)] ++;
//            }
//    }
    memset(group, -1, sizeof group);
    for (int gg = 0; gg < n; ++gg) {
        vector<int> tmp2;
        vector<int> tmp;
        REP(i,n) {
            if (r[i] <= 0 && !added[i]) {
                added[i] = 1; tmp.pb(i);
            }
        }
        for (int x : tmp)
            for (int j = 1; j<k; ++j) {
                R[F(x+j)] ++;
            }
        REP(i,n) {
            if(group[i] == -1 && R[i] <= 0) {
                group[i] = gg; tmp2.pb(i);
            }
        }
        for (int x : tmp2) {
            for (int j = 1; j<k; ++j) {
                R[F(x+j)]--;
            }
            for (int j = 1; j<k; ++j) {
                R[F(x-j)]--;
                r[F(x-j)]--;
            }
        }
//        REP(i,n) cout<<R[i]<<' ';
//        cout<<endl;
    }
//#ifdef BALBIT
    REP(i,n) {
        bug(i,group[i]);
        assert(group[i] != -1);
    }
//#endif
//    REP(i,n) bug(i,group[i]);
}

int compare_plants(int x, int y) {
    if (group[x] == group[y]) return 0;
    return group[x] > group[y] ? -1:1;
}


#ifdef BALBIT
signed main(){
    bug(1,2);
    init(3, {0, 1, 1, 2});
    bug(compare_plants(0,2));
    bug(compare_plants(1,2));
    bug(compare_plants(0,3));
    bug(compare_plants(1,3));
}
#endif

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25