Submission #1268710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268710		abdelhakim	Comparing Plants (IOI20_plants)	C++20	14 / 100	4093 ms	5700 KiB

plants

// #include <bits/stdc++.h>
// #include "plants.h"
// #define ll long long
// #define inf (ll) 1e17
// using namespace std;
// vector<ll> p;
// ll n;
// void printvec(vector<ll>& vec)
// {
//     for (auto &&e : vec)
//     {
//         cout << e << ' ';   
//     }
    
//     cout << endl;
// }
// ll maxn=2e5;
// vector<ll> tree(4*maxn+4);
// vector<ll> lazy(4*maxn+4);
// void prop(ll node, ll l, ll r)
// {
//     tree[node]+=lazy[node];
//     if(l==r)
//     {
//         lazy[node]=0;
//         return;
//     }
//     lazy[node*2+1]+=lazy[node];
//     lazy[node*2+2]+=lazy[node];
//     lazy[node]=0;
// }
// void update(ll node, ll l, ll r, ll x, ll y, ll val)
// {
//     prop(node,l,r);
//     if(max(l,x) > min(r,y)) return;
//     if(x<=l && r<=y)
//     {
//         lazy[node]+=val;
//         prop(node,l,r);
//         return;
//     }
//     ll mid=(l+r)/2;
//     update(node*2+1,l,mid,x,y,val);
//     update(node*2+2,mid+1,r,x,y,val);
//     tree[node]=min(tree[node*2+1],tree[node*2+2]);
// }
// ll query(ll node, ll l, ll r, ll x, ll y)
// {
//     prop(node,l,r);
//     if(max(l,x) > min(r,y)) return inf;
//     if(x<=l && r<=y)
//     {
//         return tree[node];
//     }
//     ll mid=(l+r)>>1;
//     return min(query(node*2+1,l,mid,x,y),query(node*2+2,mid+1,r,x,y));
// }
// void decrease(ll l, ll r)
// {
//     if(l<=r)
//     {
//         update(0,0,n-1,l,r,-1);
//     }
//     else
//     {
//         update(0,0,n-1,l,n-1,-1);
//         if(r>=0)
//         update(0,0,n-1,0,r,-1);
//     }
// }
// ll findsmallest(ll l, ll r)
// {
//     ll ans=-1;
//     ll oldl=l;
//     while(l<=r)
//     {
//         ll mid=(l+r)>>1;
//         ll vl=query(0,0,n-1,oldl,mid);
//         if(vl==0)
//         {
//             ans=mid;
//             r=mid-1;
//         }
//         else
//         {
//             l=mid+1;
//         }
//     }
//     return ans;
// }
// ll findbiggest(ll l, ll r)
// {
//     ll ans=-1;
//     ll oldr=r;
//     while(l<=r)
//     {
//         ll mid=(l+r)>>1;
//         ll vl=query(0,0,n-1,mid,oldr);
//         if(vl==0)
//         {
//             ans=mid;
//             l=mid+1;
//         }
//         else
//         {
//             r=mid-1;
//         }
//     }
//     return ans;
// }
// void init(int k, std::vector<int> r)
// {
//     n=r.size();
//     p.resize(n);
//     vector<bool> vis(n);
//     for (int i=0;i<n;i++)
//     {
//         r[i]=k-1-r[i];
//     }
//     for (int i=0;i<n;i++)
//     {
//         update(0,0,n-1,i,i,r[i]);
//     }
//     for (int i=0;i<n;i++)
//     {
//         ll ind=findsmallest(0,n-1);
//         if(ind+k<n)
//         {
//             ll vl=findsmallest(ind+k,n-1);
//             if(vl!=-1)
//             {
//                 ind=vl;
//             }
//         }
//         vis[ind]=true;
//         update(0,0,n-1,ind,ind,inf);
//         p[ind]=i;
//         decrease((ind-k+1+n)%n,ind-1);  
//     }
// }
// int compare_plants(int x, int y)
// {
//     if(p[x]<p[y]) return -1;
//     else return 1;
// }

#include <bits/stdc++.h>
#include "plants.h"
#define ll long long
#define inf (ll) 1e17
using namespace std;
vector<ll> p;
ll n;
void printvec(vector<ll>& vec)
{
    for (auto &&e : vec)
    {
        cout << e << ' ';   
    }
    
    cout << endl;
}
void init(int k, std::vector<int> r)
{
    n=r.size();
    p.resize(n);
    vector<bool> vis(n);
    for (int i=0;i<n;i++)
    {
        r[i]=k-1-r[i];
    }
    for (int i=0;i<n;i++)
    {
        ll ind=0;
        bool qrbti=false;
        for (int j=0;j<n;j++)
        {
            if(vis[j]) continue;
            if(r[j]==0&&!qrbti)
            {
                ind=j;
                j+=k-1;
                qrbti=true;
            }
            else if(r[j]==0)
            {
                ind=j;break;
            }
        }
        vis[ind]=true;
        p[ind]=i;
        for (int j=ind-1;j>=ind-k+1;j--)
        {
            ll index=j;
            if(index < 0) index+=n;
            r[index]--;
        }
        
    }
}
int compare_plants(int x, int y)
{
    if(p[x]<p[y]) return -1;
    else return 1;
}

• 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