oj.uz

Submission #61049

# Submission time Handle Problem Language Result Execution time Memory
61049 2018-07-25T06:53:34 Z 노영훈(#1760) Broken Device (JOI17_broken_device) C++11
75 / 100
 83 ms 3840 KB 
#include "Annalib.h"
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
typedef long long ll;

static int N;

void my_set(int pos, int val){
    assert(0<=pos && pos<=N-1);
    if(val!=0 && val!=1) val=0;
    Set(pos, val);
}

void Anna(int _N, ll X, int K, int P[]){
    N=_N;

    ll F[100]={}, S[100]={};
    F[0]=1, F[1]=2, S[0]=1;
    for(int i=2; i<=85; i++) F[i]=F[i-1]+F[i-2];
    for(int i=1; i<=85; i++) S[i]=S[i-1]+F[i];

    bool out[150]={};
    for(int i=0; i<K; i++) out[P[i]]=true;
    for(int i=0; i<N/2; i++) if(out[i*2] || out[i*2+1]) out[i*2]=out[i*2+1]=true;

    // cout<<"A_OUT:\n";
    // for(int i=0; i<N; i++) cout<<out[i];
    // cout<<'\n';

    int Y[150]={}; ll Z=X;
    for(int i=84; i>=0; i--){
        if(S[i]<Z) Y[i+1]=1, Z-=F[i+1];
    }
    if(Z!=0) Y[0]=1;

    // for(int i=0; i<86; i++) cout<<Y[i];
    // cout<<'\n';
    // cout<<"ASK: "<<X<<'\n';

    for(int i=0, j=0; i<N; i++){
        if(out[i]) { my_set(i, 0); continue; }
        my_set(i, Y[j++]);
    }
}

#include "Brunolib.h"
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;

ll Bruno(int N, int A[]){

    ll F[100]={}, S[100]={};
    F[0]=1, F[1]=2, S[0]=1;
    for(int i=2; i<=86; i++) F[i]=F[i-1]+F[i-2];
    for(int i=1; i<=86; i++) S[i]=S[i-1]+F[i];

    bool out[150]={};
    for(int i=0; i<N/2; i++) if(A[i*2]==0 && A[i*2+1]==0) out[i*2]=out[i*2+1]=true;
    
    // cout<<"B_OUT:\n";
    // for(int i=0; i<N; i++) cout<<out[i];
    // cout<<'\n';

    int Y[150]={}; ll Z=0;
    for(int i=0, j=0; i<N; i++){
        if(out[i]) continue;
        Y[j++]=A[i];
    }

    // for(int j=0; j<=85; j++) cout<<Y[j];
    // cout<<'\n';

    for(int i=85; i>=0; i--){
        Z+=Y[i]*F[i];
    }
    // cout<<"ANS: "<<Z<<'\n';
    return Z;
}

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 56 ms 2800 KB Output is partially correct - L* = 33
2 Partially correct 58 ms 3192 KB Output is partially correct - L* = 33
3 Partially correct 83 ms 3576 KB Output is partially correct - L* = 33
4 Partially correct 61 ms 3576 KB Output is partially correct - L* = 32
5 Partially correct 60 ms 3576 KB Output is partially correct - L* = 33
6 Partially correct 48 ms 3792 KB Output is partially correct - L* = 33
7 Partially correct 56 ms 3840 KB Output is partially correct - L* = 33
8 Partially correct 67 ms 3840 KB Output is partially correct - L* = 33
9 Partially correct 49 ms 3840 KB Output is partially correct - L* = 33
10 Partially correct 53 ms 3840 KB Output is partially correct - L* = 32
11 Partially correct 52 ms 3840 KB Output is partially correct - L* = 33
12 Partially correct 69 ms 3840 KB Output is partially correct - L* = 32
13 Partially correct 62 ms 3840 KB Output is partially correct - L* = 32
14 Partially correct 52 ms 3840 KB Output is partially correct - L* = 32
15 Partially correct 77 ms 3840 KB Output is partially correct - L* = 33
16 Partially correct 62 ms 3840 KB Output is partially correct - L* = 33
17 Partially correct 57 ms 3840 KB Output is partially correct - L* = 32
18 Partially correct 79 ms 3840 KB Output is partially correct - L* = 32
19 Partially correct 52 ms 3840 KB Output is partially correct - L* = 32
20 Partially correct 71 ms 3840 KB Output is partially correct - L* = 32
21 Partially correct 56 ms 3840 KB Output is partially correct - L* = 32
22 Partially correct 57 ms 3840 KB Output is partially correct - L* = 32
23 Partially correct 62 ms 3840 KB Output is partially correct - L* = 33
24 Partially correct 55 ms 3840 KB Output is partially correct - L* = 32
25 Partially correct 69 ms 3840 KB Output is partially correct - L* = 32
26 Partially correct 65 ms 3840 KB Output is partially correct - L* = 32
27 Partially correct 53 ms 3840 KB Output is partially correct - L* = 32
28 Partially correct 72 ms 3840 KB Output is partially correct - L* = 33
29 Partially correct 66 ms 3840 KB Output is partially correct - L* = 33
30 Partially correct 67 ms 3840 KB Output is partially correct - L* = 32
31 Partially correct 50 ms 3840 KB Output is partially correct - L* = 33
32 Partially correct 64 ms 3840 KB Output is partially correct - L* = 33
33 Partially correct 64 ms 3840 KB Output is partially correct - L* = 32
34 Partially correct 66 ms 3840 KB Output is partially correct - L* = 32
35 Partially correct 56 ms 3840 KB Output is partially correct - L* = 32
36 Partially correct 62 ms 3840 KB Output is partially correct - L* = 33
37 Partially correct 68 ms 3840 KB Output is partially correct - L* = 32
38 Partially correct 70 ms 3840 KB Output is partially correct - L* = 32
39 Partially correct 53 ms 3840 KB Output is partially correct - L* = 33
40 Partially correct 66 ms 3840 KB Output is partially correct - L* = 32