oj.uz

Submission #866175

# Submission time Handle Problem Language Result Execution time Memory
866175 2023-10-25T14:22:53 Z andrei_boaca Comparing Plants (IOI20_plants) C++17
19 / 100
 4000 ms 21428 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;
            }
        }
    }
    if(k>2)
    {
        for(int value=1;value<=n;value++)
        {
            vector<int> vals;
            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];
            }
            for(int j=0;j<n;j++)
                if(can[j]==0&&!use[j])
                    vals.push_back(j);
            assert(!vals.empty());
            for(int who:vals)
            {
                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:69:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   69 |             bool ok=0;
      |                  ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8628 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 46 ms 11304 KB Output is correct
7 Correct 50 ms 11640 KB Output is correct
8 Correct 66 ms 12588 KB Output is correct
9 Correct 59 ms 12372 KB Output is correct
10 Correct 62 ms 12368 KB Output is correct
11 Correct 66 ms 12380 KB Output is correct
12 Correct 60 ms 12600 KB Output is correct
13 Correct 56 ms 12368 KB Output is correct
14 Correct 77 ms 12372 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 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 19 ms 10844 KB Output is correct
7 Correct 472 ms 13500 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 19 ms 10844 KB Output is correct
10 Correct 450 ms 13500 KB Output is correct
11 Correct 403 ms 13480 KB Output is correct
12 Correct 398 ms 13744 KB Output is correct
13 Correct 476 ms 13496 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 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 19 ms 10844 KB Output is correct
7 Correct 472 ms 13500 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 19 ms 10844 KB Output is correct
10 Correct 450 ms 13500 KB Output is correct
11 Correct 403 ms 13480 KB Output is correct
12 Correct 398 ms 13744 KB Output is correct
13 Correct 476 ms 13496 KB Output is correct
14 Execution timed out 4046 ms 15476 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Runtime error 10 ms 21428 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Runtime error 10 ms 21340 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Runtime error 11 ms 21384 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8628 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 46 ms 11304 KB Output is correct
7 Correct 50 ms 11640 KB Output is correct
8 Correct 66 ms 12588 KB Output is correct
9 Correct 59 ms 12372 KB Output is correct
10 Correct 62 ms 12368 KB Output is correct
11 Correct 66 ms 12380 KB Output is correct
12 Correct 60 ms 12600 KB Output is correct
13 Correct 56 ms 12368 KB Output is correct
14 Correct 77 ms 12372 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 19 ms 10844 KB Output is correct
21 Correct 472 ms 13500 KB Output is correct
22 Correct 3 ms 10588 KB Output is correct
23 Correct 19 ms 10844 KB Output is correct
24 Correct 450 ms 13500 KB Output is correct
25 Correct 403 ms 13480 KB Output is correct
26 Correct 398 ms 13744 KB Output is correct
27 Correct 476 ms 13496 KB Output is correct
28 Execution timed out 4046 ms 15476 KB Time limit exceeded
29 Halted 0 ms 0 KB -