oj.uz

Submission #866172

# Submission time Handle Problem Language Result Execution time Memory
866172 2023-10-25T14:18:10 Z andrei_boaca Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 23892 KB 
#include "plants.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
vector<int> muchii[200005];
int n,bigger[200005],smaller[200005],lastsmall[200005],lastbig[200005],k,v[200005];
bool use[200005];
ll mars[500005],can[500005];
int dist(int a,int b)
{
    return (b-a+n)%n;
}
int myprv(int x)
{
    return (x-1+n)%n;
}
void init(int K, std::vector<int> 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;
            }
        }
    }
    for(int value=1;value<=n;value++)
    {
        for(int i=0;i<=2*n;i++)
        {
            mars[i]=0;
            can[i]=0;
        }
        for(int j=0;j<n;j++)
            if(!use[j])
            {
                if(r[j]==k-1)
                {
                    mars[j+1]++;
                    mars[j+k]--;
                }
                else
                    can[j]++;
            }
        bool ok=0;
        if(value==2)
            ok=1;
        for(int j=0;j<2*n;j++)
        {
            if(j>0)
                mars[j]+=mars[j-1];
            can[j%n]+=mars[j];
        }
        int who=-1;
        for(int j=0;j<n;j++)
            if(can[j]==0&&!use[j])
            {
                who=j;
                break;
            }
        assert(who>-1);
        use[who]=1;
        v[who]=value;
        for(int j=myprv(who),cnt=1;cnt<k;cnt++,j=myprv(j))
            r[j]++;
    }
}
int compare_plants(int x, int 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;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:66:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   66 |         bool ok=0;
      |              ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 42 ms 14420 KB Output is correct
7 Execution timed out 4029 ms 17744 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 17 ms 11000 KB Output is correct
7 Correct 401 ms 15528 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 17 ms 10844 KB Output is correct
10 Correct 389 ms 15440 KB Output is correct
11 Correct 335 ms 15380 KB Output is correct
12 Correct 339 ms 15636 KB Output is correct
13 Correct 410 ms 15384 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 17 ms 11000 KB Output is correct
7 Correct 401 ms 15528 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 17 ms 10844 KB Output is correct
10 Correct 389 ms 15440 KB Output is correct
11 Correct 335 ms 15380 KB Output is correct
12 Correct 339 ms 15636 KB Output is correct
13 Correct 410 ms 15384 KB Output is correct
14 Execution timed out 4027 ms 17744 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10984 KB Output is correct
3 Correct 81 ms 15256 KB Output is correct
4 Execution timed out 4053 ms 23892 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Incorrect 3 ms 10588 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 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 42 ms 14420 KB Output is correct
7 Execution timed out 4029 ms 17744 KB Time limit exceeded
8 Halted 0 ms 0 KB -