oj.uz

Submission #866257

# Submission time Handle Problem Language Result Execution time Memory
866257 2023-10-25T16:20:43 Z andrei_boaca Comparing Plants (IOI20_plants) C++17
5 / 100
 78 ms 17416 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++)
        muchii[i].clear();
    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 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 40 ms 15488 KB Output is correct
7 Correct 47 ms 15600 KB Output is correct
8 Correct 78 ms 17232 KB Output is correct
9 Correct 71 ms 17404 KB Output is correct
10 Correct 61 ms 17236 KB Output is correct
11 Correct 64 ms 17408 KB Output is correct
12 Correct 63 ms 17236 KB Output is correct
13 Correct 58 ms 17236 KB Output is correct
14 Correct 59 ms 17416 KB Output is correct

Subtask #2
0 / 14.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 12832 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 2 ms 12636 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 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12832 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 2 ms 12636 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 12636 KB Output is correct
2 Incorrect 2 ms 12636 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 12636 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 12636 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 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 40 ms 15488 KB Output is correct
7 Correct 47 ms 15600 KB Output is correct
8 Correct 78 ms 17232 KB Output is correct
9 Correct 71 ms 17404 KB Output is correct
10 Correct 61 ms 17236 KB Output is correct
11 Correct 64 ms 17408 KB Output is correct
12 Correct 63 ms 17236 KB Output is correct
13 Correct 58 ms 17236 KB Output is correct
14 Correct 59 ms 17416 KB Output is correct
15 Correct 2 ms 12632 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12832 KB Output is correct
18 Correct 2 ms 12636 KB Output is correct
19 Incorrect 2 ms 12636 KB Output isn't correct
20 Halted 0 ms 0 KB -