oj.uz

답안 #301351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
301351 2020-09-17T21:08:22 Z joseacaz 식물 비교 (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

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

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

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

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

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

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

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