oj.uz

Submission #600901

# Submission time Handle Problem Language Result Execution time Memory
600901 2022-07-21T08:59:19 Z MadokaMagicaFan Bit Shift Registers (IOI21_registers) C++17
100 / 100
 1 ms 628 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second

#define clear                       for (i = 0; i < B; ++i) { v[i] = 0; }
/* #define ONPC */

const int D = 99; // del extra
const int L = 98; // last bit
const int S = 97; // for sum
const int N = 96; // min
const int X = 95; // max
const int F = 94; // diff
const int T = 93; // temporary
const int R = 92; // removable
const int B = 2000;
const int M = 100;
vector<bitset<B>> r(M);

void append_move(int t, int y);
void append_store(int t, vector<bool> v);
void append_and(int t, int x, int y);
void append_or(int t, int x, int y);
void append_xor(int t, int x, int y);
void append_not(int t, int x);
void append_left(int t, int x, int p);
void append_right(int t, int x, int p);
void append_add(int t, int x, int y);

void
fminmax(int a, int b, int k, bool onlymin)
{
    append_not(F, b);
    append_and(F ,F, D);
    append_add(F ,F, a);
    append_and(F ,F, L);

    int s = 0;
    for (int j = 0; j < B; ++j) {
        if ((1<<(j+1))-1 > k) break;
        s = (1<<(j+1))-1;
        append_right(N, F, (1<<j));
        append_or(F,F,N);
    }

    if (s < k) {
        append_right(T, F, k-s);
        append_or(F,F,T);
    }


    if (onlymin) {
        append_and(0, F, b);
        append_not(F,F);
        append_and(T, F, a);
        append_or(0, 0, T);
    } else {
        append_and(X, F, a);
        append_and(N, F, b);
        append_xor(T, X, a);
        append_xor(F, N, b);
        append_or(N, N, T);
        append_or(X, X, F);
    }
    return;
}

int
domin(int n, int k)
{
    int i, j, l, lastbit;

    vector<bool> v(B, 0);

    lastbit = 31-__builtin_clz(n);

    for (i = n * k; i < B; ++i) v[i] = 1;

    if (n != (1<<lastbit)) {
        append_store(3,v);
        append_or(0,0,3);
        n = (1<<(1+lastbit));
    }

    clear;
    
    for (i = 0; i < n; ++i) {
        if (i&1) continue;
        for (j = 0; j < k; ++j) v[i*k+j] = 1;
    }

    append_store(D,v); clear;

    for (i = 0; i < n; ++i) {
        if (i&1) continue;
        v[i*k+k] = 1;
    }

    append_store(L,v); clear;

    int diff = k;
    int s = 0;
    while (n > 1) {
        append_and(1, s, D);
        append_right(2, s, diff);

        fminmax(1,2,k, 1);

        diff <<= 1;
        n >>= 1;
    }

    return 0;
}

void
construct_instructions(int s, int n, int k, int q)
{
    int i, j, l, it;
    if (!s) {
        domin(n,k);
        return;
    }

    vector<bool> v(B, 0);

    for (i = n * k; i < B; ++i) v[i] = 1;
    append_store(3,v); clear;
    if (n&1) {
        ++n;
        append_or(0,0,3);
    }


    it = n + 5;

    for (i = 0; i < n; ++i) {
        if (i&1) continue;
        for (j = 0; j < k; ++j) v[i*k+j] = 1;
    }

    append_store(D,v); clear;

    for (i = 0; i < n; ++i) {
        if (i&1) continue;
        v[i*k+k] = 1;
    }

    append_store(L,v); clear;

    for (i = 0; i < k; ++i) v[i] = 1;
    for (i = (n-1) * k; i < B; ++i) v[i] = 1;

    append_store(R,v); clear;

    for (i = 0; i < it; ++i) {
        if (i & 1) {
            append_right(1, 0, k);
            append_and(1, 1, D);
            append_right(2, 0, k<<1);
            append_and(2, 2, D);
            fminmax(1,2,k,0);
            append_and(0,0,R);

            append_left(T, N, k);
            append_or(0,0,T);
            append_left(T, X, k<<1);
            append_or(0,0,T);
        } else {
            append_and(1, 0, D);
            append_right(2, 0, k);
            append_and(2, 2, D);
            fminmax(1,2,k,0);

            append_move(0,N);
            append_left(T, X, k);
            append_or(0,0,T);
        }
    }


    return;
}

#ifdef ONPC
int op = 0;
void append_move(int t, int y){
    ++op;
    r[t] = r[y];
}
void append_store(int t, vector<bool> v){
    ++op;
    for (int i = 0; i < B; ++i) r[t][i] = v[i];
}

void append_and(int t, int x, int y){
    ++op;
    r[t] = (r[x]&r[y]);
}
void append_or(int t, int x, int y){
    ++op;
    r[t] = (r[x]|r[y]);
}
void append_xor(int t, int x, int y){
    ++op;
    r[t] = (r[x]^r[y]);
}
void append_not(int t, int x){
    ++op;
    r[t] = (~r[x]);
}
void append_left(int t, int x, int p){
    ++op;
    r[t] = (r[x]<<p);
}
void append_right(int t, int x, int p){
    ++op;
    r[t] = (r[x]>>p);
}
void append_add(int t, int x, int y){
    ++op;
    bitset<B> tmp;
    bool ex = 0;
    int cnt;
    for (int i = 0; i < B; ++i) {
        tmp[i] = (r[x][i]^r[y][i]^ex);
        cnt = 0;
        if (r[x][i]) ++cnt;
        if (r[y][i]) ++cnt;
        if (ex) ++cnt;

        ex = (cnt > 1);
    }

    r[t] = tmp;
}

void
solve()
{
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < B; ++j) {
            r[i][j] = 0;
        }
    }
    int n, k, x, rans;
    rans = inf;

    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        cin >> x;
        rans = min(x,rans);
        for (int j = 0; j < k; ++j)
            if ((x>>j)&1) r[0][i*k+j] = 1;
    }

    construct_instructions(1,n,k,100);

    /* int ans = 0; */
    /*  */
    /* for (int j = 0; j < n; ++j) { */
    /*     ans = 0; */
    /*     for (int i = 0; i < k; ++i) { */
    /*         if (r[0][j*k+i]) ans |= (1<<i); */
    /*     } */
    /*     cout << ans << ' '; */
    /* } */
    /* cout << endl; */

    cout << op << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Compilation message

registers.cpp: In function 'int domin(int, int)':
registers.cpp:86:15: warning: unused variable 'l' [-Wunused-variable]
   86 |     int i, j, l, lastbit;
      |               ^
registers.cpp: In function 'void construct_instructions(int, int, int, int)':
registers.cpp:134:15: warning: unused variable 'l' [-Wunused-variable]
  134 |     int i, j, l, it;
      |               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 628 KB Output is correct
4 Correct 1 ms 628 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct