oj.uz

Submission #813248

# Submission time Handle Problem Language Result Execution time Memory
813248 2023-08-07T14:36:30 Z physics07 Bit Shift Registers (IOI21_registers) C++17
100 / 100
 3 ms 1048 KB 
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<bool> v;
int b=2000, usable=3, one=1, kth=2;
void swapp(int n, int k, pair<int, int> l, pair<int, int> r) {
    int lt=usable, rt=usable+1, nl=usable+2, nr=usable+3, nnl=usable+6, nnr=usable+7;
    fill(v.begin(), v.end(), 0);
    for(int i=l.first*k; i<(l.second+1)*k; i++) v[i]=1;
    append_store(nnl, v);
    append_not(nl, nnl);
    append_and(lt, 0, nnl);
    append_right(lt, lt, l.first*k);
    fill(v.begin(), v.end(), 0);
    for(int i=r.first*k; i<(r.second+1)*k; i++) v[i]=1;
    append_store(nnr, v);
    append_not(nr, nnr);
    append_and(rt, 0, nnr);
    append_right(rt, rt, r.first*k);
    int nt=usable+4, comp=usable+5, xr=usable+8;
    append_not(nt, lt);
    append_add(nt, nt, one);
    append_add(nt, rt, nt);
    append_xor(nt, lt, nt);
    append_xor(nt, rt, nt);
    append_and(nt, nt, kth);
    append_right(comp, nt, k);
    append_not(comp, comp);
    append_add(comp, comp, one);
    append_add(comp, comp, nt);
    append_xor(xr, lt, rt);
    append_and(comp, comp, xr);
    append_xor(lt, comp, lt);
    append_xor(rt, comp, rt);
    append_left(lt, lt, l.first*k);
    append_left(rt, rt, r.first*k);
    append_and(0, 0, nl);
    append_and(0, 0, nr);
    append_and(lt, lt, nnl);
    append_and(rt, rt, nnr);
    append_or(0, lt, 0);
    append_or(0, rt, 0);
}
void solve(int n, int k, int dis, int prv) {
    int val=usable, curr=usable+1;
    int m=n/2+n%2;
    fill(v.begin(), v.end(), 0);
    for(int i=0; i<m; i++) for(int j=0; j<k; j++) v[i*(dis+k)*2+j]=1;
    append_store(val, v);
    append_and(curr, val, prv);
    append_left(val, val, k+dis);
    append_and(prv, val, prv);
    append_right(prv, prv, k+dis);
    fill(v.begin(), v.end(), 0);
    if(n%2) for(int j=0; j<k; j++) v[n/2*(dis+k)*2+j]=1;
    append_store(val, v);
    append_or(prv, val, prv);
    int not_curr=curr+1, stk=curr+2;
    append_not(not_curr, curr);
    append_add(not_curr, not_curr, one);
    append_add(stk, prv, not_curr);
    fill(v.begin(), v.end(), 0);
    for(int i=0; i<m; i++) for(int j=0; j<k; j++) v[i*(dis+k)*2+j]=1;
    for(int i=0; i<b; i++) v[i]=1-v[i];
    append_store(val, v);
    append_and(stk, stk, val);
    append_right(stk, stk, k);
    append_and(prv, prv, stk);
    append_not(stk, stk);
    append_and(curr, curr, stk);
    append_or(prv, curr, prv);
}
void findmin(int n, int k) {
    v.resize(b);
	fill(v.begin(), v.end(), 0);
	v[0]=1;
	append_store(one, v);
	int dis=0;
    while(n>1) {
        solve(n, k, dis, 0);
        n=n/2+n%2;
        dis=dis*2+k;
    }
}
void sorting(int n, int k) {
    v.resize(b);
	fill(v.begin(), v.end(), 0);
	v[0]=1;
	append_store(one, v);
	v[0]=0;
	for(int i=k; i<b; i+=k) v[i]=1;
	append_store(kth, v);
	if(n%2) {
        fill(v.begin(), v.end(), 0);
        for(int i=n*k; i<n*k+k; i++) v[i]=1;
        int s=usable;
        append_store(s, v);
        append_or(0, s, 0);
        n++;
	}
	for(int i=0; i<n/2; i++) {
        swapp(n, k, {0, n/2-1}, {n/2, n-1});
        swapp(n, k, {n/2, n-2}, {1, n/2-1});
	}
	int pnt=99;
	fill(v.begin(), v.end(), 0);
	vector<int> ord(n, 0);
	for(int i=0; i<n/2; i++) {
        ord[i]=i*2;
        ord[i+n/2]=i*2+1;
	}
	for(int i=0; i<k; i++) v[i]=1;
	append_store(pnt, v);
	fill(v.begin(), v.end(), 0);
	append_store(2, v);
	for(int i=0; i<n; i++) {
        append_and(1, 0, pnt);
        if(ord[i]>i) append_left(1, 1, k*(ord[i]-i));
        else if(ord[i]<i) append_right(1, 1, k*(i-ord[i]));
        append_or(2, 2, 1);
        append_left(pnt, pnt, k);
	}
	append_move(0, 2);
}
void construct_instructions(int s, int n, int k, int q) {
    if(!s) findmin(n, k);
    else sorting(n, k);
}

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 0 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 340 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 3 ms 1048 KB Output is correct
4 Correct 3 ms 1048 KB Output is correct
5 Correct 2 ms 792 KB Output is correct
6 Correct 2 ms 832 KB Output is correct
7 Correct 2 ms 792 KB Output is correct