oj.uz

Submission #978769

# Submission time Handle Problem Language Result Execution time Memory
978769 2024-05-09T16:33:31 Z AdamGS Bit Shift Registers (IOI21_registers) C++17
100 / 100
 1 ms 604 KB 
#include "registers.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int B=2000;
void construct_minimum(int n, int k) {
  vector<bool>T(B);
  for(int i=1; i<n; i*=2) {
    rep(j, B) T[j]=0;
    for(int j=0; j<n; j+=2*i) rep(l, k) T[j*k+l]=1;
    append_store(1, T);
    rep(j, B) T[j]=0;
    for(int j=i; j<n; j+=2*i) rep(l, k) T[j*k+l]=1;
    append_store(2, T);
    rep(j, B) T[j]=0;
    for(int j=0; j<n; j+=2*i) {
      rep(l, k) T[j*k+l]=1;
      if(j+i<n) rep(l, k) T[j*k+k+l]=1;
    }
    append_store(12, T);
    append_and(3, 0, 1);
    append_and(4, 0, 2);
    append_right(5, 4, k*i);
    append_not(6, 3);
    append_add(7, 5, 6);
    append_xor(8, 3, 5);
    append_left(9, 8, k);
    append_and(10, 7, 9);
    append_and(10, 10, 12);
    append_right(11, 10, k);
    append_xor(0, 0, 11);
  }
}
void construct_instructions(int s, int n, int k, int q) {
  if(s==0) {
    construct_minimum(n, k);
    return;
  }
  vector<bool>T(B);
  for(int i=0; i<n; i+=2) rep(j, k) T[i*k+j]=1;
  append_store(1, T); // 10101010
  rep(i, B) T[i]=0; 
  for(int i=1; i<n; i+=2) rep(j, k) T[i*k+j]=1;
  append_store(2, T); // 01010101
  rep(i, B) T[i]=0;
  for(int i=0; i<=n; i+=2) rep(j, k) T[i*k+j]=1;
  append_store(12, T);
  rep(i, B) T[i]=0;
  for(int i=1; i<=n; i+=2) rep(j, k) T[i*k+j]=1;
  append_store(13, T);
  rep(i, B) T[i]=0;
  rep(i, n*k) T[i]=1;
  append_store(14, T);
  rep(i, B) T[i]=0;
  rep(i, (n+1)*k) T[i]=1;
  append_store(15, T);
  rep(i, n) {
    if(i%2==0) {
      append_and(3, 0, 1); // a0 0 a2 0 a4 ... an 0
      append_and(4, 0, 2); // 0 a1 0 a3 0 ... 0 a(n-1)
    } else {
      append_left(0, 0, k);
      append_and(3, 0, 12);
      append_and(4, 0, 13);
    }
    append_right(5, 4, k); // a1 0 a3 0 ... a(n-1) 0
    append_not(6, 3); // a0' 1 a2' 1 a4' ... an' 1
    append_add(7, 5, 6);
    append_xor(8, 3, 5);
    append_left(9, 8, k);
    append_and(10, 7, 9);
    append_and(10, 10, 14+(i%2));
    append_xor(0, 0, 10);
    append_right(11, 10, k);
    append_xor(0, 0, 11);
    if(i%2==1) append_right(0, 0, k);
  }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
25.0 / 25.0

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

Subtask #5
13.0 / 13.0

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

Subtask #6
29.0 / 29.0

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