oj.uz

Submission #271809

# Submission time Handle Problem Language Result Execution time Memory
271809 2020-08-18T07:36:10 Z 문홍윤(#5109) Last supper (IOI12_supper) C++14
40 / 100
 448 ms 16120 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)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);
        s.insert(x);
        PutBack(t-1);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 772 KB Output is correct
2 Correct 1 ms 772 KB Output is correct
3 Correct 2 ms 772 KB Output is correct
4 Correct 8 ms 1192 KB Output is correct
5 Correct 18 ms 1492 KB Output is correct
6 Correct 17 ms 1416 KB Output is correct
7 Correct 5 ms 1024 KB Output is correct
8 Correct 17 ms 1460 KB Output is correct
9 Correct 17 ms 1600 KB Output is correct
10 Correct 11 ms 1440 KB Output is correct
11 Correct 13 ms 1368 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1860 KB Output is correct
2 Correct 133 ms 5872 KB Output is correct
3 Correct 394 ms 15088 KB Output is correct
4 Correct 448 ms 16120 KB Output is correct
5 Correct 427 ms 15460 KB Output is correct
6 Correct 379 ms 13552 KB Output is correct
7 Correct 336 ms 13040 KB Output is correct
8 Correct 336 ms 13604 KB Output is correct
9 Correct 429 ms 15532 KB Output is correct
10 Correct 303 ms 13112 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 10424 KB Output is correct
2 Correct 324 ms 12848 KB Output is correct
3 Correct 318 ms 12888 KB Output is correct
4 Correct 320 ms 12528 KB Output is correct
5 Correct 243 ms 11072 KB Output is correct
6 Correct 340 ms 12784 KB Output is correct
7 Correct 338 ms 12576 KB Output is correct
8 Correct 400 ms 15808 KB Output is correct
9 Correct 220 ms 10624 KB Output is correct
10 Correct 331 ms 12856 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1028 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 391 ms 12808 KB Output is partially correct - 875347 bits used
2 Correct 319 ms 12792 KB Output is partially correct - 841041 bits used
3 Correct 319 ms 13040 KB Output is partially correct - 807466 bits used
4 Correct 315 ms 13040 KB Output is partially correct - 806939 bits used
5 Correct 345 ms 12880 KB Output is partially correct - 805358 bits used
6 Correct 332 ms 12824 KB Output is partially correct - 807109 bits used
7 Correct 319 ms 12784 KB Output is partially correct - 805902 bits used
8 Correct 317 ms 13016 KB Output is partially correct - 808452 bits used
9 Correct 311 ms 13040 KB Output is partially correct - 807874 bits used
10 Correct 401 ms 15744 KB Output is partially correct - 1266636 bits used