oj.uz

Submission #271821

# Submission time Handle Problem Language Result Execution time Memory
271821 2020-08-18T07:38:25 Z 문홍윤(#5109) Last supper (IOI12_supper) C++14
40 / 100
 485 ms 16112 KB 
#include "advisor.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const int inf=1e9;

static int n, k, pw;
static int arr[100010];
static int tmp[100010], dp[100010];
static set<pii> s;
static int use[100010];

void ComputeAdvice(int *C, int N, int K, int M){
    n=N, k=K;
    for(pw=0; (1<<pw)<n; pw++);
    for(int i=1; i<=n; i++)arr[i]=C[i-1]+1;
    for(int i=1; i<=n; i++)tmp[i]=inf;
    for(int i=n; i>=1; i--){
        dp[i]=tmp[arr[i]];
        tmp[arr[i]]=i;
    }
    for(int i=1; i<=k; i++){
        use[i]=tmp[i];
        s.insert(mp(use[i], i));
    }
    for(int i=1; i<=n; i++){
        if(use[arr[i]]){
            s.erase(mp(use[arr[i]], arr[i]));
            use[arr[i]]=dp[i];
            s.insert(mp(use[arr[i]], arr[i]));
        }
        else{
            pii bc=*s.rbegin();
            s.erase(bc);
            use[bc.S]=0;
            use[arr[i]]=dp[i];
            s.insert(mp(use[arr[i]], arr[i]));
            for(int j=pw-1; j>=0; j--){
                if((1<<j)&(bc.S-1))WriteAdvice(1);
                else WriteAdvice(0);
            }
        }
    }
}

#include "assistant.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const int inf=1e9;

static int n, k, r, pw, re;
static unsigned char bt[2000010];

static int call(){return (int)bt[++re];}
static set<int> s;

void Assist(unsigned char *A, int N, int K, int R){
    n=N, k=K, r=R;
    for(pw=0; (1<<pw)<n; pw++);
    for(int i=1; i<=r; i++)bt[i]=A[i-1];
    for(int i=1; i<=k; i++)s.insert(i);
    for(int i=1; i<=n; i++){
        int x=GetRequest();
        x++;
        if(s.find(x)!=s.end())continue;
        int t=0;
        for(int j=0; j<pw; j++){
            t*=2;
            t+=call();
        }
        s.erase(t+1);
        s.insert(x);
        PutBack(t);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 900 KB Output is correct
2 Correct 0 ms 772 KB Output is correct
3 Correct 3 ms 948 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 19 ms 1436 KB Output is correct
6 Correct 17 ms 1288 KB Output is correct
7 Correct 7 ms 1144 KB Output is correct
8 Correct 17 ms 1464 KB Output is correct
9 Correct 18 ms 1536 KB Output is correct
10 Correct 13 ms 1448 KB Output is correct
11 Correct 15 ms 1480 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1792 KB Output is correct
2 Correct 170 ms 5616 KB Output is correct
3 Correct 391 ms 14952 KB Output is correct
4 Correct 456 ms 15952 KB Output is correct
5 Correct 444 ms 15452 KB Output is correct
6 Correct 386 ms 13472 KB Output is correct
7 Correct 395 ms 12840 KB Output is correct
8 Correct 354 ms 13368 KB Output is correct
9 Correct 485 ms 15488 KB Output is correct
10 Correct 311 ms 13040 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 10560 KB Output is correct
2 Correct 311 ms 12864 KB Output is correct
3 Correct 309 ms 12784 KB Output is correct
4 Correct 288 ms 12528 KB Output is correct
5 Correct 247 ms 10736 KB Output is correct
6 Correct 355 ms 13048 KB Output is correct
7 Correct 334 ms 12776 KB Output is correct
8 Correct 409 ms 15856 KB Output is correct
9 Correct 251 ms 11032 KB Output is correct
10 Correct 322 ms 13048 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
14.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 12840 KB Output is partially correct - 875347 bits used
2 Correct 316 ms 12952 KB Output is partially correct - 841041 bits used
3 Correct 352 ms 12896 KB Output is partially correct - 807466 bits used
4 Correct 361 ms 12960 KB Output is partially correct - 806939 bits used
5 Correct 405 ms 12784 KB Output is partially correct - 805358 bits used
6 Correct 317 ms 13040 KB Output is partially correct - 807109 bits used
7 Correct 332 ms 12904 KB Output is partially correct - 805902 bits used
8 Correct 335 ms 13040 KB Output is partially correct - 808452 bits used
9 Correct 314 ms 13040 KB Output is partially correct - 807874 bits used
10 Correct 459 ms 16112 KB Output is partially correct - 1266636 bits used