oj.uz

Submission #866261

# Submission time Handle Problem Language Result Execution time Memory
866261 2023-10-25T16:29:39 Z andrei_boaca Comparing Plants (IOI20_plants) C++17
5 / 100
 72 ms 25392 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();
        }
        if(2*k>n)
        {
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(i!=j)
                        assert(rel[i][j]!=0);
        }
        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 12748 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 47 ms 15348 KB Output is correct
7 Correct 62 ms 15688 KB Output is correct
8 Correct 72 ms 17232 KB Output is correct
9 Correct 63 ms 17236 KB Output is correct
10 Correct 63 ms 17236 KB Output is correct
11 Correct 62 ms 17420 KB Output is correct
12 Correct 63 ms 17420 KB Output is correct
13 Correct 60 ms 17408 KB Output is correct
14 Correct 72 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 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Runtime error 13 ms 25392 KB Execution killed with signal 6
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 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Runtime error 13 ms 25392 KB Execution killed with signal 6
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 12632 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 12732 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 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12748 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 47 ms 15348 KB Output is correct
7 Correct 62 ms 15688 KB Output is correct
8 Correct 72 ms 17232 KB Output is correct
9 Correct 63 ms 17236 KB Output is correct
10 Correct 63 ms 17236 KB Output is correct
11 Correct 62 ms 17420 KB Output is correct
12 Correct 63 ms 17420 KB Output is correct
13 Correct 60 ms 17408 KB Output is correct
14 Correct 72 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 12636 KB Output is correct
18 Correct 2 ms 12636 KB Output is correct
19 Runtime error 13 ms 25392 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -