oj.uz

Submission #866254

# Submission time Handle Problem Language Result Execution time Memory
866254 2023-10-25T16:11:31 Z andrei_boaca Comparing Plants (IOI20_plants) C++17
5 / 100
 65 ms 17632 KB 
#include "plants.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
int n,bigger[200005],smaller[200005],lastsmall[200005],lastbig[200005],k,v[200005];
bool use[200005],viz[200005];
ll mars[500005],can[500005];
int rel[305][305];
vector<int> muchii[200005];
vector<int> R;
int dist(int a,int b)
{
    return (b-a+n)%n;
}
int myprv(int x)
{
    return (x-1+n)%n;
}
struct aint
{
    int maxim,minim,pozmax,pozmin;
    int toprop;
} arb[3][4*200005];
vector<int> who;
aint combine(aint a,aint b)
{
    aint rez;
    rez.toprop=0;
    rez.maxim=a.maxim;
    rez.pozmax=a.pozmax;
    if(b.maxim>rez.maxim)
    {
        rez.maxim=b.maxim;
        rez.pozmax=b.pozmax;
    }

    rez.minim=a.minim;
    rez.pozmin=a.pozmin;
    if(b.minim<rez.minim)
    {
        rez.minim=b.minim;
        rez.pozmin=b.pozmin;
    }
    return rez;
}
void prop(int ind,int nod)
{
    int val=arb[ind][nod].toprop;
    arb[ind][nod*2].toprop+=val;
    arb[ind][nod*2].maxim+=val;
    arb[ind][nod*2].minim+=val;

    arb[ind][nod*2+1].toprop+=val;
    arb[ind][nod*2+1].maxim+=val;
    arb[ind][nod*2+1].minim+=val;
}
void build(int ind,int nod,int st,int dr)
{
    arb[ind][nod].toprop=0;
    if(st==dr)
    {
        arb[ind][nod].minim=arb[ind][nod].maxim=R[st]*(ind==1);
        arb[ind][nod].pozmin=arb[ind][nod].pozmax=st;
        return;
    }
    int mij=(st+dr)/2;
    build(ind,nod*2,st,mij);
    build(ind,nod*2+1,mij+1,dr);
    arb[ind][nod]=combine(arb[ind][nod*2],arb[ind][nod*2+1]);
}
void update(int ind,int nod,int st,int dr,int a,int b,int val)
{
    if(st!=dr)
        prop(ind,nod);
    arb[ind][nod].toprop=0;
    if(st>=a&&dr<=b)
    {
        arb[ind][nod].maxim+=val;
        arb[ind][nod].minim+=val;
        arb[ind][nod].toprop+=val;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(ind,nod*2,st,mij,a,b,val);
    if(b>mij)
        update(ind,nod*2+1,mij+1,dr,a,b,val);
    arb[ind][nod]=combine(arb[ind][nod*2],arb[ind][nod*2+1]);
}
void getwho(int ind,int nod,int st,int dr,int a,int b)
{
    if(st!=dr)
        prop(ind,nod);
    arb[ind][nod].toprop=0;
    if(arb[ind][nod].maxim<k-1)
        return;
    if(st==dr)
    {
        who.push_back(st);
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        getwho(ind,nod*2,st,mij,a,b);
    if(b>mij)
        getwho(ind,nod*2+1,mij+1,dr,a,b);
}
void plsadd(int ind,int st,int lg,int val)
{
    if(st+lg-1<=n-1)
    {
        update(ind,1,0,n-1,st,st+lg-1,val);
        return;
    }
    update(ind,1,0,n-1,st,n-1,val);
    update(ind,1,0,n-1,0,(st+lg-1)%n,val);
}
void guesswho(int ind,int st,int lg)
{
    who.clear();
    if(st+lg-1<=n-1)
    {
        getwho(ind,1,0,n-1,st,st+lg-1);
        return;
    }
    getwho(ind,1,0,n-1,st,n-1);
    getwho(ind,1,0,n-1,0,(st+lg-1)%n);
}
void dfs(int nod,int start)
{
    if(nod!=start)
    {
        rel[nod][start]=1;
        rel[start][nod]=-1;
    }
    use[nod]=1;
    for(int i:muchii[nod])
        if(!use[i])
            dfs(i,start);
}
void recalc()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            rel[i][j]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            use[j]=0;
        dfs(i,i);
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(rel[i][j]!=0)
                rel[j][i]=-rel[i][j];
    for(int i=0;i<n;i++)
    {
        bigger[i]=R[i];
        smaller[i]=k-1-R[i];
        for(int cnt=1,j=(i+1)%n;cnt<=k-1;cnt++,j=(j+1)%n)
        {
            if(rel[i][j]==-1)
                bigger[i]--;
            if(rel[i][j]==1)
                smaller[i]--;
        }
        for(int j=0;j<n;j++)
            if(rel[i][j]==-1)
                muchii[i].push_back(j);
    }
}
void init(int K, std::vector<int> r)
{
    R=r;
    n=r.size();
    k=K;
    for(int i=0;i<n;i++)
    {
        lastbig[i]=-1;
        lastsmall[i]=-1;
    }
    for(int i=0;i<n;i++)
    {
        if(r[i]==0)
        {
            int j=(i-1+n)%n;
            while(r[j]==1)
            {
                lastsmall[j]=i;
                j=(j-1+n)%n;
            }
        }
        if(r[i]==1)
        {
            int j=(i-1+n)%n;
            while(r[j]==0)
            {
                lastbig[j]=i;
                j=(j-1+n)%n;
            }
        }
    }
    if(n<=300)
    {
        for(int i=0;i<n;i++)
        {
            bigger[i]=r[i];
            smaller[i]=k-1-r[i];
        }
        while(true)
        {
            int x=-1;
            for(int i=0;i<n;i++)
                if(!viz[i]&&min(smaller[i],bigger[i])==0)
                {
                    x=i;
                    break;
                }
            if(x==-1)
                break;
            viz[x]=1;
            for(int i=(x+1)%n,cnt=1;cnt<=k-1;cnt++,i=(i+1)%n)
                if(rel[x][i]==0)
                {
                    if(bigger[x]>0)
                    {
                        bigger[x]--;
                        muchii[x].push_back(i);
                    }
                    else
                    {
                        smaller[x]--;
                        muchii[i].push_back(x);
                    }
                }
            recalc();
        }
        return;
    }
    if(k>2)
    {
        build(1,1,0,n-1);
        build(2,1,0,n-1);
        for(int i=0;i<n;i++)
        {
            if(r[i]==k-1)
                plsadd(2,(i+1)%n,k-1,1);
            else
                plsadd(2,i,1,1);
        }
        for(int value=1;value<=n;value++)
        {
            int poz=arb[2][1].pozmin;
            assert(arb[2][1].minim==0);
            v[poz]=value;
            plsadd(2,poz,1,1e6);
            plsadd(2,(poz+1)%n,k-1,-1);
            plsadd(1,poz,1,-1e6);
            int p=(poz-(k-1)+n)%n;
            plsadd(1,p,k-1,1);
            guesswho(1,p,k-1);
            for(auto i:who)
            {
                plsadd(2,i,1,-1);
                plsadd(2,(i+1)%n,k-1,1);
            }
        }
    }
}
int compare_plants(int x, int y)
{
    if(n<=300)
        return rel[x][y];
    if(k==2)
    {
        if(lastsmall[x]!=-1&&dist(x,y)+dist(y,lastsmall[x])==dist(x,lastsmall[x]))
            return -1;
        if(lastbig[x]!=-1&&dist(x,y)+dist(y,lastbig[x])==dist(x,lastbig[x]))
            return 1;
        if(lastsmall[y]!=-1&&dist(y,x)+dist(x,lastsmall[y])==dist(y,lastsmall[y]))
            return 1;
        if(lastbig[y]!=-1&&dist(y,x)+dist(x,lastbig[y])==dist(y,lastbig[y]))
            return -1;
        return 0;
    }
    if(v[x]<v[y])
        return -1;
    if(v[x]>v[y])
        return 1;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 40 ms 15544 KB Output is correct
7 Correct 51 ms 15700 KB Output is correct
8 Correct 64 ms 17408 KB Output is correct
9 Correct 62 ms 17236 KB Output is correct
10 Correct 62 ms 17236 KB Output is correct
11 Correct 62 ms 17244 KB Output is correct
12 Correct 65 ms 17232 KB Output is correct
13 Correct 60 ms 17232 KB Output is correct
14 Correct 63 ms 17632 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 40 ms 15544 KB Output is correct
7 Correct 51 ms 15700 KB Output is correct
8 Correct 64 ms 17408 KB Output is correct
9 Correct 62 ms 17236 KB Output is correct
10 Correct 62 ms 17236 KB Output is correct
11 Correct 62 ms 17244 KB Output is correct
12 Correct 65 ms 17232 KB Output is correct
13 Correct 60 ms 17232 KB Output is correct
14 Correct 63 ms 17632 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Correct 2 ms 12728 KB Output is correct
17 Correct 2 ms 12636 KB Output is correct
18 Correct 2 ms 12636 KB Output is correct
19 Incorrect 3 ms 12632 KB Output isn't correct
20 Halted 0 ms 0 KB -