Submission #1018131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018131		YassirSalama	Bit Shift Registers (IOI21_registers)	C++17	23 / 100	6 ms	1368 KiB

registers

#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define endl "\n"
using ull=unsigned long long;
using ll=long long;
using pii=pair<int,int>;
const int mod=1e9+7;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
template <typename T> istream& operator>>(istream& is, vector<T> &a) {
    copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;}
#ifdef IOI
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int b=2000;
#define p append_print
int k;
int n;
void set1(int i,vector<bool>& v){
	for(int j=i;j<=i+k-1;j++) v[j]=1;
}
vector<bool> clear(b,0);
#define cls append_store(50,clear);
void min(int i,int j){
	vector<bool> v(b,0);
	set1(i*k,v);
	append_store(98,v);
	append_and(2,99,98);//a[0]
	append_right(2,2,i*k);//x
    // p(2);
	v.assign(b,0);
	set1(j*k,v);
	append_store(98,v);
	append_and(3,99,98);
	append_right(3,3,j*k);//y
    append_move(11,3);
    append_move(10,2);
    // p(3);
	//comparaison
	append_not(4,3);
	append_add(4,4,97);//not y + 1
	append_add(5,4,2);//bin(x - y)
	append_right(6,5,k);//bin(x-y)>>k
	append_and(7,5,6);
	append_add(2,3,7);
    append_move(0,2);
    append_xor(1,0,10);
    append_xor(1,1,11);
}
void remove(int t,int i){
    vector<bool> v(b,1);
    for(int j=i;j<=i+k-1;j++){
        v[j]=0;
    }
    append_store(63,v);
    append_and(t,t,63);
}
void bubblesort(){
	for(int _=0;_<n;_++){
		cls
        vector<bool> v(b,0);
        set1(n*k,v);
        append_store(20,v);
        append_or(99,99,20);
        // p(99);
		for(int j=0;j+1<n;j++){
			min(j,j+1);
			//1 is the min between them
            // dbg(j,j+1)
            // p(0);
            // p(1);
			append_left(0,0,j*k);
            remove(99,j*k);
            remove(99,(j+1)*k);
            // p(99);
			append_or(99,99,0);
            append_left(1,1,k*(j+1));
            append_or(99,99,1);
            // p(99);
		}
        // p(99);
        // break;
	}
    append_move(0,99);
}
void construct_instructions(int s, int _n, int _k, int q) {k=_k;n=_n;
	append_move(99,0);
	vector<bool> v(b,0);
	set1(0,v);
	append_store(98,v);
	append_and(0,99,98);//a[0]
	v.assign(b,0);
	v[0]=1;
	append_store(97,v);
    // min(1,2);
	bubblesort();
	return;
	for(int j=1;j<n;j++){
		append_move(2,99);
		v.assign(b,0);
		set1(j*k,v);
		append_store(98,v);
		append_and(2,2,98);
		append_right(2,2,j*k);//y
		append_not(3,2);
		append_add(3,3,97);//not y + 1
		append_add(4,3,0);//bin(x - y)
		append_right(5,4,k);//bin(x-y)>>k
		append_and(6,4,5);
		append_add(0,2,6);
	}
	 
	
}
 
//used reg : 0,1,2,3
 
 
 
#ifdef IOI
#include "registers.h"
 
#ifdef _MSC_VER
#   define NORETURN __declspec(noreturn)
#elif defined __GNUC__
#   define NORETURN __attribute__ ((noreturn))
#else
#   define NORETURN
#endif
 
 
static const int m = 100;
static const int id_move = 0;
static const int id_store = 1;
static const int id_and = 2;
static const int id_or = 3;
static const int id_xor = 4;
static const int id_not = 5;
static const int id_left = 6;
static const int id_right = 7;
static const int id_add = 8;
static const int id_print = 9;
 
static int s, q;
static int instruction_count = 0;
static std::bitset<b> reg[m];
 
static inline void load_register(std::bitset<b>& bs, std::vector<int>& v) {
    bs.reset();
    for (int i = 0; i < (int)v.size(); i++) {
        for (int j = 0; j < k; j++) {
            bs[i * k + j] = (v[i] & (1 << j));
        }
    }
}
 
static inline void unload_register(std::bitset<b>& bs, std::vector<int>& v) {
    v.assign(v.size(), 0);
    for (int i = 0; i < (int)v.size(); i++) {
        for (int j = 0; j < k; j++) {
            v[i] |= (bs[i * k + j] << j);
        }
    }
}
 
static void execute_move(int t, int x) {
    reg[t] = reg[x];
}
 
static void execute_store(int t, std::vector<bool> v) {
    for(int i=0; i<b; i++) {
        reg[t][i] = v[i]; // bit-by-bit copy
    }
}
 
static void execute_and(int t, int x, int y) {
    reg[t] = (reg[x]&reg[y]);
}
 
static void execute_or(int t, int x, int y) {
    reg[t] = (reg[x]|reg[y]);
}
 
static void execute_xor(int t, int x, int y) {
    reg[t] = (reg[x]^reg[y]);
}
 
static void execute_not(int t, int x) {
    reg[t] = (~reg[x]);
}
 
static void execute_left(int t, int x, int p) {
    reg[t] = (reg[x]<<p);
}
 
static void execute_right(int t, int x, int p) {
    reg[t] = (reg[x]>>p);
}
 
static void execute_add(int t, int x, int y) {
    std::bitset<b> tmp;
    bool carry = false;
    for(int i = 0; i < b; i++) {
        tmp[i] = (reg[x][i] ^ reg[y][i] ^ carry);
        carry = (reg[x][i] & reg[y][i]) || (reg[x][i] & carry) || (reg[y][i] & carry); // discard the last carry
    }
    reg[t] = tmp;
}
 
static void execute_print(int t) {
    std::vector<int> v(n);
    unload_register(reg[t], v);
    printf("register %d: ", t);
    bitset<12> c;
    for(int i=0;i<12;i++){
    	if(reg[t].test(i)) c.set(i);
    }
    cout<<c.to_string()<<endl;
}
 
struct instruction {
    int type, t, x, y;
    std::vector<bool> v;
 
    instruction(int _type): type(_type), t(-1), x(-1), y(-1) {}
 
    void execute() {
        switch(type) {
            case id_move:
                execute_move(t, x);
                break;
            case id_store:
                execute_store(t, v);
                break;
            case id_and:
                execute_and(t, x, y);
                break;
            case id_or:
                execute_or(t, x, y);
                break;
            case id_xor:
                execute_xor(t, x, y);
                break;
            case id_not:
                execute_not(t, x);
                break;
            case id_left:
                execute_left(t, x, y);
                break;
            case id_right:
                execute_right(t, x, y);
                break;
            case id_add:
                execute_add(t, x, y);
                break;
            case id_print:
                execute_print(t);
                break;
            default:
                assert(false);
        }
    }
    void print() {
    	#ifndef IOI
        switch(type) {
            case id_move:
                printf("move %d %d\n", t, x);
                break;
            case id_store:
                printf("store %d ", t);
                for(int i=0; i<b; i++) {
                    putchar(v[i]+'0');
                }
                putchar('\n');
                break;
            case id_and:
                printf("and %d %d %d\n", t, x, y);
                break;
            case id_or:
                printf("or %d %d %d\n", t, x, y);
                break;
            case id_xor:
                printf("xor %d %d %d\n", t, x, y);
                break;
            case id_not:
                printf("not %d %d\n", t, x);
                break;
            case id_left:
                printf("left %d %d %d\n", t, x, y);
                break;
            case id_right:
                printf("right %d %d %d\n", t, x, y);
                break;
            case id_add:
                printf("add %d %d %d\n", t, x, y);
                break;
            case id_print:
                printf("print %d\n", t);
                break;
            default:
                assert(false);
        }
        #endif
    }
};
 
static std::vector<instruction> instructions;
 
NORETURN static inline void error(std::string reason) {
    printf("%s\n", reason.c_str());
    fflush(stdout);
    exit(0);
}
 
static inline void check_instructions() {
    if (instruction_count >= q) {
        error("Too many instructions");
    }
}
 
static inline void check_index(int index) {
    if (index < 0 || index >= m) {
        error("Invalid index");
    }
}
 
void append_move(int t, int x) {
    check_instructions();
    check_index(t);
    check_index(x);
    instruction i(id_move);
    i.t = t;
    i.x = x;
    instruction_count++;
    instructions.push_back(i);
}
 
void append_store(int t, std::vector<bool> v) {
    check_instructions();
    check_index(t);
    if ((int)v.size() != b) {
        error("Value to store is not b bits long");
    }
    instruction i(id_store);
    i.t = t;
    i.v = v;
    instruction_count++;
    instructions.push_back(i);
}
 
void append_and(int t, int x, int y) {
    check_instructions();
    check_index(t);
    check_index(x);
    check_index(y);
    instruction i(id_and);
    i.t = t;
    i.x = x;
    i.y = y;
    instruction_count++;
    instructions.push_back(i);
}
 
void append_or(int t, int x, int y) {
    check_instructions();
    check_index(t);
    check_index(x);
    check_index(y);
    instruction i(id_or);
    i.t = t;
    i.x = x;
    i.y = y;
    instruction_count++;
    instructions.push_back(i);
}
 
void append_xor(int t, int x, int y) {
    check_instructions();
    check_index(t);
    check_index(x);
    check_index(y);
    instruction i(id_xor);
    i.t = t;
    i.x = x;
    i.y = y;
    instruction_count++;
    instructions.push_back(i);
}
 
void append_not(int t, int x) {
    check_instructions();
    check_index(t);
    check_index(x);
    instruction i(id_not);
    i.t = t;
    i.x = x;
    instruction_count++;
    instructions.push_back(i);
}
 
void append_left(int t, int x, int p) {
    check_instructions();
    check_index(t);
    check_index(x);
    if (p < 0 || p > b) {
        error("Invalid shift value");
    }
    instruction i(id_left);
    i.t = t;
    i.x = x;
    i.y = p;
    instruction_count++;
    instructions.push_back(i);
}
 
void append_right(int t, int x, int p) {
    check_instructions();
    check_index(t);
    check_index(x);
    if (p < 0 || p > b) {
        error("Invalid shift value");
    }
    instruction i(id_right);
    i.t = t;
    i.x = x;
    i.y = p;
    instruction_count++;
    instructions.push_back(i);
}
 
void append_add(int t, int x, int y) {
    check_instructions();
    check_index(t);
    check_index(x);
    check_index(y);
    instruction i(id_add);
    i.t = t;
    i.x = x;
    i.y = y;
    instruction_count++;
    instructions.push_back(i);
}
 
void append_print(int t) {
    check_index(t);
    instruction i(id_print);
    i.t = t;
    instructions.push_back(i);
}
 
int main() {
    assert(4 == scanf("%d %d %d %d", &s, &n, &k, &q));
 
    construct_instructions(s, n, k, q);
    for(instruction &i : instructions) {
        i.print();
    }
    std::vector<int> a(n);
    bool exited = false;
    while (true) {
        for (int i = 0; i < n; i++) {
            assert(1 == scanf("%d", &a[i]));
            if (i == 0 && a[i] == -1) {
                fflush(stdout);
                exited = true;
                break;
            }
        }
        if (exited) break;
        load_register(reg[0], a);
        for (int i = 1; i < m; i++) {
            reg[i].reset();
        }
        for (instruction& i : instructions) {
            i.execute();
        }
        unload_register(reg[0], a);
        if (s == 0) {
            printf("%d\n", a[0]);
        } else {
            for (int i = 0; i < n; i++) {
                printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
            }
        }
    }
    printf("number of instructions: %d\n", instruction_count);
    return 0;
}
#endif

• Subtask 1: 10 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 25
• Subtask 5: 13 / 13
• Subtask 6: 0 / 29