oj.uz

Submission #301351

# Submission time Handle Problem Language Result Execution time Memory
301351 2020-09-17T21:08:22 Z joseacaz Comparing Plants (IOI20_plants) C++17
14 / 100
 730 ms 106488 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;
typedef vector<int> vi;

const int MAXN = 5e3 + 5;
int N, k, vis[MAXN], memo[MAXN][MAXN], MP[MAXN][MAXN], in[MAXN], pos[MAXN];
vi r, Graph[MAXN];

void sub(int idx)
{
    for(int i = 1; i < k; i++)
    {
        int id = ((idx - i)%N + N)%N;
        if(r[id] > 0)
        {
            r[id]--;
            if(r[id] == 0 && !vis[id] && !MP[idx][id])
            {
                Graph[idx].pb(id);
                in[id]++;
                MP[idx][id] = 1;
            }
        }
    }
}

int getnext(int idx)
{
    for(int i = 1; i < N; i++)
    {
        int id = ((idx + i)%N + N)%N;
        if(i < k && !vis[id] && !MP[idx][id])
        {
                Graph[idx].pb(id);
                MP[idx][id] = 1;
                in[id]++;
        }
        if(r[id] == 0 && !vis[id])
            return id;
    }
    return idx;
}

/*
void dfs(int root, int node)
{
    memo[root][node] = 1;
    for(auto i : Graph[node])
        if(i != node && !memo[root][i])
            dfs(root, i);
}
*/

void topo()
{
    queue<int> Q;
    for(int i = 0; i < N; i++)
        if(in[i] == 0)
            Q.push(i);
    
    int cnt = 0;
    while(!Q.empty())
    {
        int node = Q.front();
        Q.pop();
        pos[node] = cnt++;
        for(auto i : Graph[node])
        {
            if(in[i] > 0)
                in[i]--;
            if(in[i] == 0)
                Q.push(i);
        }
    }
}

void init(int _k, vi _r)
{
    k = _k;
    swap(r, _r);
    N = r.size();
    
    int maxIdx = 0;
    for(int i = 0; i < N; i++)
    {
        if(r[i] != 0)
            continue;
        int maxim = 1;
        for(int j = 1; j < k; j++)
        {
            int id = ((i - j)%N + N)%N;
            if(r[id] == 0)
                maxim = 0;
        }
        if(maxim)
            maxIdx = i;
    }
    
    while(!vis[maxIdx])
    {
        vis[maxIdx] = 1;
        sub(maxIdx);
        maxIdx = getnext(maxIdx);
    }
    
    topo();
    return;
}

int compare_plants(int x, int y)
{
    if(pos[x] < pos[y])
        return 1;
    else if(pos[y] < pos[x])
        return -1;
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 31 ms 8576 KB Output is correct
7 Correct 653 ms 105212 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 27 ms 8064 KB Output is correct
10 Correct 621 ms 100416 KB Output is correct
11 Correct 297 ms 33708 KB Output is correct
12 Correct 560 ms 60756 KB Output is correct
13 Correct 730 ms 106488 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 31 ms 8576 KB Output is correct
7 Correct 653 ms 105212 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 27 ms 8064 KB Output is correct
10 Correct 621 ms 100416 KB Output is correct
11 Correct 297 ms 33708 KB Output is correct
12 Correct 560 ms 60756 KB Output is correct
13 Correct 730 ms 106488 KB Output is correct
14 Runtime error 77 ms 5884 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Incorrect 102 ms 11512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Incorrect 1 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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