Submission #629775

#	Time	Username	Problem	Language	Result	Execution time	Memory
629775		Cross_Ratio	Bit Shift Registers (IOI21_registers)	C++17	33 / 100	2 ms	844 KiB

registers

//#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
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 append_print(int t);
//m = 100, b = 2000
void swapping(int a, int b, int n, int k) {
    a--;
    b--;
    if(a==b) return;
    int i, j;
    vector<bool> mask1(2000, false), mask2(2000, false);
    vector<bool> mask3(2000, true);
    for(i=k*a;i<k*(a+1);i++) {
        mask1[i] = true;
        mask3[i] = false;
    }
    for(i=k*b;i<k*(b+1);i++) {
        mask2[i] = true;
        mask3[i] = false;
    }
    append_store(7, mask1);
    append_store(8, mask2);
    vector<bool> one(2000, false);
    one[0] = true;
    append_store(9, one);
    append_print(9);
    append_print(0);
    append_and(1, 0, 7);
    append_and(2, 0, 8);
    append_store(12, mask3);
    append_and(0,0,12);
    append_right(1, 1, k*a);
    append_right(2, 2, k*b);
    append_print(1);
    append_print(2);
    append_not(3, 1);
    append_add(4, 2, 3);
    append_right(4, 4, 2000-k);
    append_and(5, 4, 2);
    append_and(6, 4, 1);
    append_not(3, 2);
    append_add(4, 1, 3);
    append_add(4, 4, 9);
    append_right(4, 4, 2000-k);
    append_and(10, 4, 1);
    append_and(11, 4, 2);
    append_add(1, 5, 10);
    append_add(2, 6, 11);
    append_print(5);
    append_print(6);
    append_print(10);
    append_print(11);
    if(a>b) swap(a, b);
    append_print(1);
    append_print(2);
    append_left(1, 1, k*a);
    append_left(2, 2, k*b);
    append_or(0,0,1);
    append_or(0,0,2);
    append_print(0);
}
void comparing(int n, int k) {
    append_xor(3, 1, 2);
    int i, j;
    append_move(4, 3);
    for(i=0;i<k;i++) {
        append_right(4,4,1);
        append_or(3,3,4);
    }
    append_right(3, 3, 1);
    append_not(3, 3);
    append_and(5, 1, 3);
    append_and(6, 2, 3);
    append_move(7, 5);
    append_move(8, 6);
    for(i=0;i<k;i++) {
        append_right(7, 7, 1);
        append_or(5, 5, 7);
        append_right(8,8,1);
        append_or(6,6,8);
    }
    append_and(9, 1, 5);
    append_and(10, 2, 6);
    append_add(11, 9, 10);
    append_not(5, 5);
    append_not(6, 6);
    append_and(9, 1, 5);
    append_and(10, 2, 6);
    append_add(12, 9, 10);
    append_move(1, 12);
    append_move(2, 11); // 1 min 2 max
}
vector<bool> mask[605], bmask[605];
void construct_instructions(int s, int n, int k, int q) {
if(s==0) {
    append_print(0);
    int i, j;
    append_left(0, 0, 2000-n*k);
    append_right(1,0,2000-k);
    append_left(0,0,k);
    append_print(0);
    append_print(1);
    vector<bool> v(2000);
    for(i=0;i<2000;i++) {
        if(!i) v[i] = 1;
        else v[i] = 0;
    }
    append_store(7, v);
    for(i=n-2;i>=0;i--) {
        append_print(0);
        append_right(2,0,2000-k);
        append_not(3, 1);
        append_add(4, 2, 3);
        append_right(4, 4, 2000-k);
        append_and(5, 4, 2);
        append_not(3, 2);
        append_add(4, 1, 3);
        append_add(4, 4, 7);
        append_right(4, 4, 2000-k);
        append_and(6, 4, 1);
        append_add(1, 5, 6);
        append_left(0,0,k);
        append_print(1);
    }
    append_move(0, 1);
    append_print(0);
}
else {
    int i, j;
    for(i=0;i<200;i++) mask[i].resize(2000);
    for(i=0;i<200;i++) bmask[i].resize(2000);
    for(i=0;i<200;i++) {
        for(j=i*k;j<(i+1)*k;j++) mask[i][j] = true;
    }
    for(i=0;i<200;i++) {
        for(j=0;j<2000;j++) bmask[i][j] = 1;
    }
    for(i=0;i<200;i++) {
        for(j=i*k;j<(i+1)*k;j++) bmask[i][j] = 0;
    }
    for(i=1;i<n;i++) {
        vector<bool> vis(n, false);
        vector<pair<int,int>> Query;
        for(j=0;j<n;j++) {
            if(!vis[j]&&!vis[(i+j)%n]) {
                vis[j] = true;
                vis[(i+j)%n] = true;
                Query.push_back(pair<int,int>(min(i,(i+j)%n),max(i,(i+j)%n)));
            }
        }
        vector<bool> empt(2000, false);
        append_store(1, empt);
        append_store(2, empt);
        for(i=0;i<Query.size();i++) {
            int s1 = Query[i].first;
            int s2 = Query[i].second;
            append_store(3, mask[s1]);
            append_store(4, mask[s2]);
            append_and(3, 0, 3);
            append_and(4, 0, 4);
            append_right(3, 3, k*s1);
            append_right(4, 4, k*s2);
            append_left(3, 3, 3*k*i);
            append_left(4, 4, 3*k*i);
            append_or(1, 3, 3);
            append_or(2, 4, 4);
        }
        comparing(n, k);
        for(i=0;i<Query.size();i++) {
            int s1 = Query[i].first;
            int s2 = Query[i].second;
            append_store(3, mask[3*i]);
            append_store(4, mask[3*i]);
            append_and(3, 3, 1);
            append_and(4, 4, 2);
            append_right(3, 3, 3*k*i);
            append_right(4, 4, 3*k*i);
            append_left(3, 3, k*s1);
            append_left(4, 4, k*s2);
            append_store(5, bmask[s1]);
            append_store(6, bmask[s2]);
            append_and(0, 0, 5);
            append_and(0, 0, 6);
            append_or(0, 0, 3);
            append_or(0, 0, 4);
        }
    }
}
}

Compilation message (stderr)

registers.cpp: In function 'void swapping(int, int, int, int)':
registers.cpp:19:12: warning: unused variable 'j' [-Wunused-variable]
   19 |     int i, j;
      |            ^
registers.cpp: In function 'void comparing(int, int)':
registers.cpp:73:12: warning: unused variable 'j' [-Wunused-variable]
   73 |     int i, j;
      |            ^
registers.cpp: In function 'void construct_instructions(int, int, int, int)':
registers.cpp:106:12: warning: unused variable 'j' [-Wunused-variable]
  106 |     int i, j;
      |            ^
registers.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for(i=0;i<Query.size();i++) {
      |                 ~^~~~~~~~~~~~~
registers.cpp:178:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         for(i=0;i<Query.size();i++) {
      |                 ~^~~~~~~~~~~~~

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