Submission #303229

#	Time	Username	Problem	Language	Result	Execution time	Memory
303229		qiangbao	Comparing Plants (IOI20_plants)	C++14	14 / 100	4054 ms	10944 KiB

plants

#include <iostream>
#include <vector>
#include <set>
#include "plants.h"

#define pb push_back

using namespace std;

int n;

set<int> zero;
set<int> cur;
set<int>:: iterator it, it2;

int ans[200001];

void init(int k, vector<int> r)
{
    int i, j;
    n=r.size();
    
    for(i=0;i<n;i++)
        r[i]=k-1-r[i];
    for(i=0;i<n;i++)
        if(r[i]==0)
            zero.insert(i), zero.insert(i+n);
    for(i=1;i<=n;i++){
        it=zero.begin();
        while(it!=zero.end() && *it<n){
            it2=it, it2++;
            if(*it2-*it>=k){
                int f=*it2;
                if(f>=n) f-=n;
                ans[f]=i;
                zero.erase(f), zero.erase(f+n);
                for(j=0;j<k;j++){
                    int f2=(f-j);
                    if(f2<0)
                        f2+=n;
                    r[f2]--;
                    if(r[f2]==0)
                        zero.insert(f2), zero.insert(f2+n);
                }
                break;
            }
            it2=it;
            it=zero.lower_bound(*it+k), it--;
            if(it==it2) it++;
        }
    }
}

int compare_plants(int x, int y)
{
    if(ans[x]==ans[y])
        return 0;
    else if(ans[x]>ans[y])
        return 1;
    return -1;
}

//int main()
//{
//    int nn;
//    vector<int> in, in2;
//    int i, j;
//
//    cin >> nn;
//    for(i=0;i<nn;i++){
//        int x;
//        cin >> x;
//        in.pb(x), in2.pb(0);
//    }
//
//    for(i=0;i<nn;i++)
//        for(j=1;j<4;j++){
//            int f=(i+j)%nn;
//            if(in[i]<in[f])
//                in2[i]++;
//        }
//
//    init(4, in2);
//    for(i=0;i<n;i++)
//        cout << ans[i] << " ";
//    cout << endl;
//
//    return 0;
//}

//7
// 4 3 5 7 6 1 2

• 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