oj.uz

Submission #7281

# Submission time Handle Problem Language Result Execution time Memory
7281 2014-07-29T08:04:57 Z myungwoo Last supper (IOI12_supper) C++
100 / 100
 114 ms 43928 KB 
#include "advisor.h"
#include <queue>
using namespace std;

#define MAXN 100005
typedef pair<int,int> pii;

static int C[MAXN];
static int in_scaffold[MAXN],recent[MAXN],next_[MAXN],first_active[MAXN],request_active[MAXN],request_num[MAXN];
static priority_queue<pii> que;

void ComputeAdvice(int *arr, int N, int K, int M)
{
    int i,k;
    for (i=0;i<N;i++) C[i+1] = arr[i]+1;
    for (i=1;i<=N;i++) next_[i] = 1e9;
    for (i=N;i;i--){
        recent[i] = next_[C[i]];
        next_[C[i]] = i;
    }
    for (i=1;i<=K;i++) in_scaffold[i] = 1, que.push(pii(next_[i],i));
    for (i=1;i<=K;i++) first_active[i] = 0;
    for (i=1;i<=N;i++) request_active[i] = 0;
    for (i=1;i<=N;i++){
        if (in_scaffold[C[i]]){
            if (request_num[C[i]]) request_active[request_num[C[i]]] = 1;
            else first_active[C[i]] = 1;
            request_num[C[i]] = i;
            que.push(pii(recent[i],C[i]));
            continue;
        }
        k = que.top().second; que.pop();
        in_scaffold[C[i]] = 1; in_scaffold[k] = 0;
        request_num[C[i]] = i;
        que.push(pii(recent[i],C[i]));
    }
    for (i=1;i<=K;i++) WriteAdvice(first_active[i]);
    for (i=1;i<=N;i++) WriteAdvice(request_active[i]);
}

#include "assistant.h"
#include <queue>
using namespace std;

#define MAXN 100005

static int in_scaffold[MAXN],first_active[MAXN],request_active[MAXN];
static bool in_que[MAXN];
static queue<int> que;

void Assist(unsigned char *A, int N, int K, int R)
{
    int i,j,k,p=0;
    for (i=1;i<=K;i++) in_scaffold[i] = 1;
    for (i=1;i<=K;i++){
        first_active[i] = A[p++];
        if (!first_active[i]) in_que[i] = 1, que.push(i);
    }
    for (i=1;i<=N;i++) request_active[i] = A[p++];
    for (i=1;i<=N;i++){
        int req=GetRequest()+1;
        if (request_active[i]) in_que[req] = 0;
        if (!request_active[i] && !in_que[req]) in_que[req] = 1, que.push(req);
        if (in_scaffold[req]) continue;
        for (;;){
            k = que.front(); que.pop();
            if (in_que[k]) break;
        }
        in_que[k] = 0;
        in_scaffold[req] = 1;
        in_scaffold[k] = 0;
        PutBack(--k);
    }
}

Compilation message

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:13:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,k,p=0;
           ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 4 ms 1232 KB Output is correct
3 Correct 4 ms 1320 KB Output is correct
4 Correct 6 ms 1848 KB Output is correct
5 Correct 7 ms 1848 KB Output is correct
6 Correct 7 ms 1848 KB Output is correct
7 Correct 8 ms 2144 KB Output is correct
8 Correct 8 ms 2232 KB Output is correct
9 Correct 8 ms 2280 KB Output is correct
10 Correct 7 ms 2448 KB Output is correct
11 Correct 7 ms 2496 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3056 KB Output is correct
2 Correct 49 ms 6952 KB Output is correct
3 Correct 111 ms 12824 KB Output is correct
4 Correct 88 ms 12824 KB Output is correct
5 Correct 76 ms 13712 KB Output is correct
6 Correct 94 ms 15328 KB Output is correct
7 Correct 102 ms 17128 KB Output is correct
8 Correct 74 ms 17128 KB Output is correct
9 Correct 73 ms 17880 KB Output is correct
10 Correct 94 ms 20744 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 20744 KB Output is correct
2 Correct 103 ms 22656 KB Output is correct
3 Correct 108 ms 23760 KB Output is correct
4 Correct 110 ms 25168 KB Output is correct
5 Correct 93 ms 26320 KB Output is correct
6 Correct 97 ms 27208 KB Output is correct
7 Correct 98 ms 28616 KB Output is correct
8 Correct 90 ms 29264 KB Output is correct
9 Correct 78 ms 31208 KB Output is correct
10 Correct 92 ms 32168 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32168 KB Output is correct
2 Correct 8 ms 32168 KB Output is correct
3 Correct 7 ms 32168 KB Output is correct
4 Correct 8 ms 32168 KB Output is correct
5 Correct 9 ms 32168 KB Output is correct
6 Correct 8 ms 32168 KB Output is correct
7 Correct 11 ms 32168 KB Output is correct
8 Correct 7 ms 32168 KB Output is correct
9 Correct 8 ms 32168 KB Output is correct
10 Correct 7 ms 32168 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 33496 KB Output is correct - 120000 bits used
2 Correct 87 ms 34912 KB Output is correct - 122000 bits used
3 Correct 101 ms 36048 KB Output is correct - 125000 bits used
4 Correct 108 ms 37224 KB Output is correct - 125000 bits used
5 Correct 99 ms 38416 KB Output is correct - 125000 bits used
6 Correct 114 ms 39568 KB Output is correct - 125000 bits used
7 Correct 87 ms 40712 KB Output is correct - 124828 bits used
8 Correct 106 ms 41976 KB Output is correct - 124910 bits used
9 Correct 88 ms 43024 KB Output is correct - 125000 bits used
10 Correct 94 ms 43928 KB Output is correct - 125000 bits used