oj.uz

Submission #169486

# Submission time Handle Problem Language Result Execution time Memory
169486 2019-12-20T15:57:42 Z arnold518 Last supper (IOI12_supper) C++14
20 / 100
 461 ms 29824 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

static int *C, N, K, M, B, D[MAXN+10], P[MAXN+10];
static vector<int> T[MAXN+10];

void ComputeAdvice(int *_C, int _N, int _K, int _M)
{
    int i, j;
    C=_C; N=_N; K=_K; M=_M;

    for(i=20; i>=0; i--) if(N&(1<<i)) break;
    B=i+1;

    for(i=0; i<N; i++) T[C[i]].push_back(i);
    for(i=0; i<N; i++) T[i].push_back(N);

    set<pii, greater<pii>> PQ;
    for(i=0; i<K; i++)
    {
        PQ.insert({*upper_bound(T[i].begin(), T[i].end(), -1), i});
        P[i]=1;
    }

    for(i=0; i<N; i++)
    {
        if(P[C[i]])
        {
            PQ.erase({i, C[i]});
            PQ.insert({*upper_bound(T[C[i]].begin(), T[C[i]].end(), i), C[i]});
            D[i]=(1<<B)-1;
        }
        else
        {
            D[i]=PQ.begin()->second;
            P[PQ.begin()->second]=0;
            PQ.erase(PQ.begin());
            PQ.insert({*upper_bound(T[C[i]].begin(), T[C[i]].end(), i), C[i]});
            P[C[i]]=1;
        }
    }

    for(i=0; i<N; i++)
    {
        for(j=0; j<B; j++)
        {
            if(D[i]&(1<<j)) WriteAdvice(1);
            else WriteAdvice(0);
        }
    }
}

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

static int N, K, R, B, D[MAXN+10];
unsigned char *A;

void Assist(unsigned char *_A, int _N, int _K, int _R)
{
    int i, j;
    A=_A; N=_N; K=_K; R=_R;

    for(i=20; i>=0; i--) if(N&(1<<i)) break;
    B=i+1;

    int cnt=0;
    for(i=0; i<N; i++) for(j=0; j<B; j++) if(A[cnt++]) D[i]|=(1<<j);

    for(i=0; i<N; i++)
    {
        GetRequest();
        if(D[i]!=(1<<B)-1) PutBack(D[i]);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5360 KB Output is correct
2 Correct 6 ms 5360 KB Output is correct
3 Correct 9 ms 5616 KB Output is correct
4 Correct 15 ms 5872 KB Output is correct
5 Correct 22 ms 6384 KB Output is correct
6 Correct 22 ms 6128 KB Output is correct
7 Correct 20 ms 6384 KB Output is correct
8 Correct 22 ms 6384 KB Output is correct
9 Correct 23 ms 6384 KB Output is correct
10 Correct 22 ms 6384 KB Output is correct
11 Correct 23 ms 6384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7408 KB Output is correct
2 Correct 200 ms 16288 KB Output is correct
3 Correct 437 ms 29824 KB Output is correct
4 Correct 418 ms 26624 KB Output is correct
5 Correct 444 ms 26872 KB Output is correct
6 Correct 426 ms 27376 KB Output is correct
7 Correct 461 ms 28480 KB Output is correct
8 Correct 368 ms 25584 KB Output is correct
9 Correct 405 ms 27128 KB Output is correct
10 Correct 448 ms 29536 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 23536 KB Output is correct
2 Incorrect 106 ms 20464 KB Error - advice is too long
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5872 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
3.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 27808 KB Output is partially correct - 1700000 bits used
2 Correct 438 ms 27408 KB Output is partially correct - 1700000 bits used
3 Correct 439 ms 27800 KB Output is partially correct - 1700000 bits used
4 Correct 437 ms 27736 KB Output is partially correct - 1700000 bits used
5 Correct 441 ms 27632 KB Output is partially correct - 1700000 bits used
6 Correct 453 ms 27832 KB Output is partially correct - 1700000 bits used
7 Correct 437 ms 28144 KB Output is partially correct - 1697263 bits used
8 Correct 461 ms 27952 KB Output is partially correct - 1700000 bits used
9 Correct 431 ms 27784 KB Output is partially correct - 1700000 bits used
10 Correct 430 ms 27632 KB Output is partially correct - 1700000 bits used