oj.uz

Submission #271728

# Submission time Handle Problem Language Result Execution time Memory
271728 2020-08-18T07:21:39 Z 문홍윤(#5109) Last supper (IOI12_supper) C++14
0 / 100
 463 ms 16312 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)<=k; pw++);
    for(int i=1; i<=n; i++)arr[i]=C[i-1]+1;
    for(int i=1; i<=k; 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)<=k; 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;
        if(s.size()<k){
            PutBack(x-1);
            s.insert(x);
            continue;
        }
        int t=0;
        for(int j=0; j<pw; j++){
            t*=2;
            t+=call();
        }
        s.erase(t);
        s.insert(x);
        PutBack(t-1);
    }
}

Compilation message

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:34:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         if(s.size()<k){
      |            ~~~~~~~~^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1016 KB Error - Putting back a color that is not on the scaffold
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 1916 KB Error - Putting back a color that is not on the scaffold
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 338 ms 12056 KB Error - Putting back a color that is not on the scaffold
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 411 ms 14952 KB Error - Putting back a color that is not on the scaffold
2 Incorrect 393 ms 15088 KB Error - Putting back a color that is not on the scaffold
3 Incorrect 347 ms 14576 KB Error - Putting back a color that is not on the scaffold
4 Incorrect 347 ms 14576 KB Error - Putting back a color that is not on the scaffold
5 Incorrect 385 ms 14712 KB Error - Putting back a color that is not on the scaffold
6 Incorrect 410 ms 14616 KB Error - Putting back a color that is not on the scaffold
7 Incorrect 386 ms 14576 KB Error - Putting back a color that is not on the scaffold
8 Incorrect 378 ms 14576 KB Error - Putting back a color that is not on the scaffold
9 Incorrect 375 ms 14568 KB Error - Putting back a color that is not on the scaffold
10 Incorrect 463 ms 16312 KB Error - Putting back a color that is not on the scaffold