Skip to content

Instantly share code, notes, and snippets.

@wiwiho

wiwiho/dna.cpp Secret

Created Jun 25, 2021
Embed
What would you like to do?
IOI 2021 day 2
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<vector<int>>> cnt;
map<char, int> id;
void init(string a, string b) {
n = a.size();
id['A'] = 0;
id['T'] = 1;
id['C'] = 2;
a = ' ' + a;
b = ' ' + b;
cnt.resize(3, vector<vector<int>>(3, vector<int>(n + 1)));
for(int i = 1; i <= n; i++){
cnt[id[a[i]]][id[b[i]]][i]++;
for(int t1 = 0; t1 < 3; t1++){
for(int t2 = 0; t2 < 3; t2++) cnt[t1][t2][i] += cnt[t1][t2][i - 1];
}
}
}
int get_distance(int x, int y) {
x++; y++;
vector<vector<int>> now(3, vector<int>(3));
vector<int> c1(3), c2(3);
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
now[i][j] = cnt[i][j][y] - cnt[i][j][x - 1];
c1[i] += now[i][j];
c2[j] += now[i][j];
}
}
for(int i = 0; i < 3; i++){
if(c1[i] != c2[i]) return -1;
}
int ans = 0;
for(int i = 0; i < 3; i++){
for(int j = i + 1; j < 3; j++){
int tmp = min(now[i][j], now[j][i]);
now[i][j] -= tmp;
now[j][i] -= tmp;
ans += tmp;
}
}
int tv = -1;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
if(i == j || now[i][j] == 0) continue;
if(tv == -1) tv = now[i][j];
assert(tv == now[i][j]);
}
}
if(tv == -1) return ans;
ans += tv * 2;
return ans;
}
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> w, s;
vector<vector<int>> go;
vector<ll> ss;
vector<vector<ll>> ps, mx;
int SZ = 30;
int n;
void init(int _n, vector<int> _s, vector<int> p, vector<int> _w, vector<int> l) {
n = _n;
s = _s;
w = _w;
ss.resize(n + 1);
ps.resize(n + 1, vector<ll>(SZ));
go.resize(n + 1, vector<int>(SZ));
mx.resize(n + 1, vector<ll>(SZ));
for(int i = n - 1; i >= 0; i--){
ss[i] = s[i];
if(w[i] != n) ss[i] += ss[w[i]];
go[i][0] = l[i];
ps[i][0] = p[i];
mx[i][0] = s[i] - 1;
}
go[n][0] = n;
for(int i = 1; i < SZ; i++){
for(int j = 0; j <= n; j++){
go[j][i] = go[go[j][i - 1]][i - 1];
ps[j][i] = ps[j][i - 1] + ps[go[j][i - 1]][i - 1];
mx[j][i] = min(mx[j][i - 1], mx[go[j][i - 1]][i - 1] - ps[j][i - 1]);
}
}
}
ll simulate(int now, int _z){
ll z = _z;
while(now < n && z < 10000000){
for(int i = SZ - 1; i >= 0; i--){
if(z > mx[now][i]) continue;
z += ps[now][i];
now = go[now][i];
}
assert(z >= s[now]);
z += s[now];
now = w[now];
}
z += ss[now];
return z;
}
#include "dungeons.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;
vector<int> w, s;
vector<vector<int>> go;
vector<ll> ss;
vector<vector<ll>> ps, mx;
ll mxs = 0;
int SZ = 30;
int n;
void init(int _n, vector<int> _s, vector<int> p, vector<int> _w, vector<int> l) {
n = _n;
s = _s;
w = _w;
ss.resize(n + 1);
ps.resize(n + 1, vector<ll>(SZ));
go.resize(n + 1, vector<int>(SZ));
mx.resize(n + 1, vector<ll>(SZ));
w.eb(n);
s.eb();
for(int i = n - 1; i >= 0; i--){
mxs = max(mxs, (ll)s[i]);
ss[i] = s[i];
if(w[i] != n) ss[i] += ss[w[i]];
go[i][0] = l[i];
ps[i][0] = p[i];
mx[i][0] = s[i] - 1;
}
go[n][0] = n;
for(int i = 1; i < SZ; i++){
for(int j = 0; j <= n; j++){
go[j][i] = go[go[j][i - 1]][i - 1];
ps[j][i] = ps[j][i - 1] + ps[go[j][i - 1]][i - 1];
mx[j][i] = min(mx[j][i - 1], mx[go[j][i - 1]][i - 1] - ps[j][i - 1]);
}
}
}
ll simulate(int now, int _z){
ll z = _z;
while(now < n && z < mxs){
for(int i = SZ - 1; i >= 0; i--){
if(z > mx[now][i]) continue;
z += ps[now][i];
now = go[now][i];
}
z += s[now];
now = w[now];
}
z += ss[now];
return z;
}
#include "dungeons.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
using namespace std;
typedef long long ll;
vector<int> w, s;
vector<vector<vector<int>>> go;
vector<ll> ss;
vector<vector<vector<ll>>> ps, mx;
vector<int> discr;
ll mxs = 0;
int SZ = 30;
int sz;
int n;
const ll MAX = 1LL << 60;
int gd(int v){
return lower_bound(iter(discr), v) - discr.begin();
}
void init(int _n, vector<int> _s, vector<int> p, vector<int> _w, vector<int> l) {
n = _n;
s = _s;
w = _w;
w.eb(n);
l.eb(n);
s.eb();
p.eb();
discr = s;
lsort(discr);
uni(discr);
sz = discr.size();
ss.resize(n + 1);
ps.resize(sz, vector<vector<ll>>(n + 1, vector<ll>(SZ)));
go.resize(sz, vector<vector<int>>(n + 1, vector<int>(SZ)));
mx.resize(sz, vector<vector<ll>>(n + 1, vector<ll>(SZ)));
for(int i = n; i >= 0; i--){
mxs = max(mxs, (ll)s[i]);
ss[i] = s[i];
if(w[i] != n) ss[i] += ss[w[i]];
int id = gd(s[i]);
for(int j = 0; j < sz; j++){
if(j >= id){
go[j][i][0] = w[i];
ps[j][i][0] = s[i];
mx[j][i][0] = MAX;
continue;
}
go[j][i][0] = l[i];
ps[j][i][0] = p[i];
mx[j][i][0] = s[i] - 1;
}
}
for(int k = 0; k < sz; k++){
for(int i = 1; i < SZ; i++){
for(int j = 0; j <= n; j++){
go[k][j][i] = go[k][go[k][j][i - 1]][i - 1];
ps[k][j][i] = ps[k][j][i - 1] + ps[k][go[k][j][i - 1]][i - 1];
mx[k][j][i] = min(mx[k][j][i - 1], mx[k][go[k][j][i - 1]][i - 1] - ps[k][j][i - 1]);
}
}
}
}
ll simulate(int now, int _z){
ll z = _z;
while(now < n && z < mxs){
int k = upper_bound(iter(discr), z) - discr.begin();
k--;
for(int i = SZ - 1; i >= 0; i--){
if(z > mx[k][now][i]) continue;
z += ps[k][now][i];
now = go[k][now][i];
}
z += s[now];
now = w[now];
}
z += ss[now];
return z;
}
#include "dungeons.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;
vector<int> w, s, l, p;
vector<vector<int>> gol, gow;
vector<vector<ll>> ss, mn;
vector<vector<ll>> ps, mx;
int SZ = 30;
int n;
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n = _n;
s = _s;
w = _w;
p = _p;
l = _l;
s.eb();
p.eb();
w.eb(n);
l.eb(n);
ps.resize(n + 1, vector<ll>(SZ));
gol.resize(n + 1, vector<int>(SZ));
mx.resize(n + 1, vector<ll>(SZ));
ss.resize(n + 1, vector<ll>(SZ));
gow.resize(n + 1, vector<int>(SZ));
mn.resize(n + 1, vector<ll>(SZ));
for(int i = 0; i <= n; i++){
ps[i][0] = p[i];
ss[i][0] = s[i];
gol[i][0] = l[i];
gow[i][0] = w[i];
mx[i][0] = s[i] - 1;
mn[i][0] = s[i];
}
for(int i = 1; i < SZ; i++){
for(int j = 0; j <= n; j++){
gol[j][i] = gol[gol[j][i - 1]][i - 1];
ps[j][i] = ps[j][i - 1] + ps[gol[j][i - 1]][i - 1];
mx[j][i] = min(mx[j][i - 1], mx[gol[j][i - 1]][i - 1] - ps[j][i - 1]);
gow[j][i] = gow[gow[j][i - 1]][i - 1];
ss[j][i] = ss[j][i - 1] + ss[gow[j][i - 1]][i - 1];
mn[j][i] = max(mn[j][i - 1], mn[gow[j][i - 1]][i - 1] - ss[j][i - 1]);
}
}
}
ll simulate(int now, int _z){
ll z = _z;
while(now < n){
if(z < s[now]){
for(int i = SZ - 1; i >= 0; i--){
if(z > mx[now][i]) continue;
z += ps[now][i];
now = gol[now][i];
}
}
else{
for(int i = SZ - 1; i >= 0; i--){
if(z < mn[now][i]) continue;
z += ss[now][i];
now = gow[now][i];
}
}
}
return z;
}
#include "registers.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;
int n, k;
void getmin(){
append_xor(3, 1, 2);
append_move(4, 3);
for(int i = 0; (1 << i) < k; i++){
append_right(5, 4, 1 << i);
append_or(4, 4, 5);
}
append_not(5, 4);
append_right(5, 5, 1);
append_and(4, 4, 5);
// high bit of 3 at 4
append_print(3);
append_print(4);
append_and(5, 1, 4);
for(int i = 0; (1 << i) < k; i++){
append_right(6, 5, 1 << i);
append_or(5, 5, 6);
}
append_and(5, 3, 5);
append_xor(1, 1, 5);
append_and(5, 2, 4);
for(int i = 0; (1 << i) < k; i++){
append_right(6, 5, 1 << i);
append_or(5, 5, 6);
}
append_and(5, 3, 5);
append_xor(2, 2, 5);
}
void construct_instructions(int s, int _n, int _k, int q) {
n = _n;
k = _k;
vector<bool> msk(2000);
for(int i = 0; i < k; i++) msk[i] = true;
append_store(99, msk);
append_move(1, 0);
append_and(1, 1, 99);
for(int i = 1; i < n; i++){
append_right(2, 0, k * i);
append_and(2, 2, 99);
getmin();
}
append_move(0, 1);
}
#include "registers.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;
int n, k;
void getmin(){
append_xor(3, 0, 1);
append_move(4, 3);
for(int i = 0; (1 << i) < k; i++){
append_right(5, 4, 1 << i);
append_or(4, 4, 5);
}
append_not(5, 4);
append_right(5, 5, 1);
append_and(4, 4, 5);
// high bit of 3 at 4
append_print(3);
append_print(4);
append_and(5, 0, 4);
for(int i = 0; (1 << i) < k; i++){
append_right(6, 5, 1 << i);
append_or(5, 5, 6);
}
append_and(5, 3, 5);
append_xor(0, 0, 5);
append_and(5, 1, 4);
for(int i = 0; (1 << i) < k; i++){
append_right(6, 5, 1 << i);
append_or(5, 5, 6);
}
append_and(5, 3, 5);
append_xor(1, 1, 5);
}
void construct_instructions(int s, int _n, int _k, int q) {
n = _n;
k = _k;
vector<bool> msk(2000);
for(int i = 0; i < k; i++) msk[i] = true;
append_store(99, msk);
append_right(1, 0, k);
append_and(0, 0, 99);
getmin();
}
#include "registers.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;
int n, k;
void getmin(int a, int b){
append_print(a);
append_print(b);
append_xor(11, a, b);
append_move(12, 11);
for(int i = 0; (1 << i) < k; i++){
append_right(13, 12, 1 << i);
append_or(12, 12, 13);
}
append_not(13, 12);
append_right(13, 13, 1);
append_and(12, 12, 13);
// high bit of 11 at 12
append_print(11);
append_print(12);
append_and(13, a, 12);
for(int i = 0; (1 << i) < k; i++){
append_right(14, 13, 1 << i);
append_or(13, 13, 14);
}
append_and(13, 11, 13);
append_xor(a, a, 13);
append_xor(b, a, 11);
append_print(a);
append_print(b);
}
void construct_instructions(int s, int _n, int _k, int q) {
n = _n;
k = _k;
assert(n <= 10 && s == 1);
vector<bool> msk(2000);
for(int i = 0; i < k; i++) msk[i] = true;
append_store(99, msk);
for(int i = 1; i <= n; i++){
append_right(i, 0, k * (i - 1));
append_and(i, i, 99);
}
for(int i = 0; i < n - 1; i++){
for(int j = 0; j < n - i - 1; j++){
getmin(j + 1, j + 2);
}
}
append_move(0, 1);
for(int i = 2; i <= n; i++){
append_left(i, i, k * (i - 1));
append_or(0, 0, i);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment