oj.uz

Submission #866252

# Submission time Handle Problem Language Result Execution time Memory
866252 2023-10-25T16:06:33 Z andrei_boaca Comparing Plants (IOI20_plants) C++17
5 / 100
 76 ms 17424 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++)
        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 12632 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 2 ms 12636 KB Output is correct
6 Correct 37 ms 15520 KB Output is correct
7 Correct 47 ms 15700 KB Output is correct
8 Correct 67 ms 17388 KB Output is correct
9 Correct 65 ms 17408 KB Output is correct
10 Correct 67 ms 17404 KB Output is correct
11 Correct 72 ms 17416 KB Output is correct
12 Correct 76 ms 17236 KB Output is correct
13 Correct 56 ms 17416 KB Output is correct
14 Correct 56 ms 17424 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 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 3 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 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 3 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 12852 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 12632 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 2 ms 12636 KB Output is correct
6 Correct 37 ms 15520 KB Output is correct
7 Correct 47 ms 15700 KB Output is correct
8 Correct 67 ms 17388 KB Output is correct
9 Correct 65 ms 17408 KB Output is correct
10 Correct 67 ms 17404 KB Output is correct
11 Correct 72 ms 17416 KB Output is correct
12 Correct 76 ms 17236 KB Output is correct
13 Correct 56 ms 17416 KB Output is correct
14 Correct 56 ms 17424 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12632 KB Output is correct
18 Correct 2 ms 12636 KB Output is correct
19 Incorrect 3 ms 12636 KB Output isn't correct
20 Halted 0 ms 0 KB -