oj.uz

답안 #866172

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
866172 2023-10-25T14:18:10 Z andrei_boaca 식물 비교 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -