Submission #813248

#	Time	Username	Problem	Language	Result	Execution time	Memory
813248		physics07	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	3 ms	1048 KiB

registers

#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 / 10
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 25 / 25
• Subtask 5: 13 / 13
• Subtask 6: 29 / 29