Skip to content

Instantly share code, notes, and snippets.

@msg555
msg555 / linkcut.cpp
Created November 8, 2012 20:43
Solution to http://www.spoj.pl/ranks/DYNACON1/ implementing a fairly fast link-cut tree.
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
template<class T> struct splnode {
typedef splnode<T> node_t;
@msg555
msg555 / gist:4242182
Created December 8, 2012 22:04
Computes RSK tableau in O(N sqrt(N) log(N)) time
vector<vector<int> > bounded_rsk(const vector<int>& A, int k) {
vector<vector<int> > h(k);
for(int i = 0; i < A.size(); i++) {
int x = A[i];
for(int j = 0; j < k; j++) {
int p = lower_bound(h[j].begin(), h[j].end(), x) - h[j].begin();
if(p == h[j].size()) {
h[j].push_back(x);
break;
} else {
@msg555
msg555 / game.cpp
Last active April 9, 2020 17:35
Problem "Game" From IOI 2013 Day 2
#include "game.h"
#define MAXR 1000000000
#define MAXC 1000000000
#include <assert.h>
#include <stddef.h>
long long gcd2(long long X, long long Y) {
if(X == 0 || Y == 0) {
@msg555
msg555 / subframe_callback.as
Created January 21, 2020 03:44
Sample script using the subframe callback API.
class script : callback_base {
scene@ g;
array<dustman@> players;
script() {
@g = get_scene();
}
void step(int num_entities) {
int nc = num_cameras();
@msg555
msg555 / 16.cpp
Created December 17, 2019 04:04
16 dumb
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int mexp(int v, int e, int MOD) {
int ret = 1;
if (e == 0) return ret;
for(int i = 31 - __builtin_clz(e); i >= 0; i--) {
@msg555
msg555 / 10-integral.cpp
Created December 11, 2019 21:52
Float free solution to Advent Day 10
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
@msg555
msg555 / intcode.py
Last active December 8, 2019 07:46
Solution to day 7
import abc
import asyncio
import itertools
import sys
class Instruction(metaclass=abc.ABCMeta):
PARAMS = 0
def __init__(self, comp, offset, mode):
@msg555
msg555 / geo.cpp
Last active July 17, 2018 16:11
Mark's geometry routines
#include <algorithm>
#include <vector>
#include <complex>
#include <cmath>
using namespace std;
/* A flag used by some geometry routines to indicate exceptional circumstances.
*/
static bool geoerror;
class script {
scene@ g;
textfield@ txt;
int init_filth;
int init_filth_block;
int init_enemy;
script() {
@g = get_scene();
@msg555
msg555 / sounddemo.cpp
Created October 20, 2017 18:46
An example of how to embed and use custom sounds with dustscripting.
const string EMBED_sound1 = "test1.ogg";
class script {
scene@ g;
script() {
@g = get_scene();
}
void build_sounds(message@ msg) {