oj.uz

Submission #23144

# Submission time Handle Problem Language Result Execution time Memory
23144 2017-05-03T14:13:07 Z duongthoi1999 Broken Device (JOI17_broken_device) C++14
100 / 100
 49 ms 4644 KB 
#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> ii;
const int mod = (int) 1e9 + 7;

int f[150];
vector<int> mp2[4];
vector<int> mp1[3];
vector<int> b;

void Anna( int N, long long X, int K, int P[] ){
    mp2[0] = {0, 1, 0}; /// 00
    mp2[1] = {1, 0, 1}; /// 10
    mp2[2] = {1, 1, 0}; /// 01
    mp2[3] = {1, 1, 1}; /// 11
    mp1[0] = {0, 0, 1}; /// 0
    mp1[1] = {0, 1, 1}; /// 1
    mp1[2] = {1, 0, 0}; /// 1

    rep(i, 0, N) f[i] = 0;
    rep(i, 0, K) f[P[i]] = 1;
    b.clear();
    while (X > 0) {
        b.pb(X % 2);
        X /= 2;
    }
    while (SZ(b) < N) b.pb(0);
    int j = 0;
    for (int i = 0; i < N; i += 3) {
        int x = f[i] + f[i + 1] + f[i + 2];
        if(x > 1 || j == SZ(b)) {
            rep(t, 0, 3) Set(i + t, 0);
            continue;
        }
        if(x == 1) {
            if(f[i]) {
                int s = b[j];
                if(s) rep(t, 0, 3) Set(i + t, mp1[1][t]);
                else rep(t, 0, 3) Set(i + t, mp1[0][t]);
                j ++;
            }
            else if(f[i + 1]){
                int s = b[j];
                if(s) rep(t, 0, 3) Set(i + t, mp1[2][t]);
                else rep(t, 0, 3) Set(i + t, mp1[0][t]);
                j ++;
            }
            else {
                int s = b[j];
                if(s) rep(t, 0, 3) Set(i + t, mp1[2][t]);
                else {
                    s += 2 * b[j + 1];
                    rep(t, 0, 3) Set(i + t, mp2[s][t]);
                }
                if(b[j]) j ++;
                else j += 2;
            }
        }
        else {
            int s = b[j] + 2 * b[j + 1];
            j += 2;
            rep(t, 0, 3) Set(i + t, mp2[s][t]);
        }
    }
}

//
//001 -> 0
//010 -> 1
//
//
//000
//001
//010
//011
//
//100
//101
//110
//111
//
//


#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> ii;
const int mod = (int) 1e9 + 7;
ll pw[151];
int val[8], cnt[8];

long long Bruno( int N, int A[] ){
    val[1] = 1, cnt[1] = 1;
    val[2] = 0, cnt[2] = 2;
    val[3] = 2, cnt[3] = 2;
    val[4] = 0, cnt[4] = 1;
    val[5] = 1, cnt[5] = 2;
    val[6] = 1, cnt[6] = 1;
    val[7] = 3, cnt[7] = 2;

    ll res = 0;
    int j = 0;
    pw[0] = 1;
    rep(i, 1, 151) pw[i] = pw[i - 1] * 2;
    for (int i = 0; i < N; i += 3) {
        int s = A[i] + A[i + 1] * 2 + A[i + 2] * 4;
        if(s == 0) continue;
        res += val[s] * pw[j];
        j += cnt[s];
    }
    return res;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4644 KB Output is correct - L* = 40
2 Correct 46 ms 4644 KB Output is correct - L* = 40
3 Correct 32 ms 4644 KB Output is correct - L* = 40
4 Correct 35 ms 4644 KB Output is correct - L* = 40
5 Correct 32 ms 4644 KB Output is correct - L* = 40
6 Correct 39 ms 4644 KB Output is correct - L* = 40
7 Correct 34 ms 4644 KB Output is correct - L* = 40
8 Correct 25 ms 4644 KB Output is correct - L* = 40
9 Correct 35 ms 4644 KB Output is correct - L* = 40
10 Correct 35 ms 4644 KB Output is correct - L* = 40
11 Correct 27 ms 4644 KB Output is correct - L* = 40
12 Correct 35 ms 4644 KB Output is correct - L* = 40
13 Correct 35 ms 4644 KB Output is correct - L* = 40
14 Correct 35 ms 4644 KB Output is correct - L* = 40
15 Correct 35 ms 4644 KB Output is correct - L* = 40
16 Correct 32 ms 4644 KB Output is correct - L* = 40
17 Correct 39 ms 4644 KB Output is correct - L* = 40
18 Correct 38 ms 4644 KB Output is correct - L* = 40
19 Correct 35 ms 4644 KB Output is correct - L* = 40
20 Correct 41 ms 4644 KB Output is correct - L* = 40
21 Correct 35 ms 4644 KB Output is correct - L* = 40
22 Correct 28 ms 4644 KB Output is correct - L* = 40
23 Correct 35 ms 4644 KB Output is correct - L* = 40
24 Correct 49 ms 4644 KB Output is correct - L* = 40
25 Correct 39 ms 4644 KB Output is correct - L* = 40
26 Correct 32 ms 4644 KB Output is correct - L* = 40
27 Correct 32 ms 4644 KB Output is correct - L* = 40
28 Correct 39 ms 4644 KB Output is correct - L* = 40
29 Correct 35 ms 4644 KB Output is correct - L* = 40
30 Correct 35 ms 4644 KB Output is correct - L* = 40
31 Correct 28 ms 4644 KB Output is correct - L* = 40
32 Correct 32 ms 4644 KB Output is correct - L* = 40
33 Correct 32 ms 4644 KB Output is correct - L* = 40
34 Correct 32 ms 4644 KB Output is correct - L* = 40
35 Correct 39 ms 4644 KB Output is correct - L* = 40
36 Correct 38 ms 4644 KB Output is correct - L* = 40
37 Correct 32 ms 4644 KB Output is correct - L* = 40
38 Correct 35 ms 4644 KB Output is correct - L* = 40
39 Correct 32 ms 4644 KB Output is correct - L* = 40
40 Correct 35 ms 4644 KB Output is correct - L* = 40