r/backtickbot • u/backtickbot • Mar 08 '21
https://np.reddit.com/r/programminghorror/comments/m019mq/so_this_is_the_source_code_of_the_official/gq5vr0o/
Tried to pretty it up and add comments
TLDR; Looks like it's reading a file and permuting arrays in the file
#include <bits/stdc++.h>
using namespace std;
ifstream in_file("permutare.in");
ofstream out_file("permutare.out");
cosnt unsigned INFINITY = 2000000001;
unsigned n,m,c,u,v,p,q,x[2010];
int main() {
// Initialize matrix for dynamic programming
unsigned D[1000][1000];
D[0][0]=1;
for(int i = 1; i < 1000; i++) {
D[i][0] = 1; // set first value in each row to 1
for(int k = 1; k <= i; k++) {
// every value in DP matrix is either sum of left and above or infinity
// [0 0 ... 0 0]
// [1 1 ... 1 1]
// [1 2 3 4 ...]
// [1 3 6 10 ...]
// ...
// [1 999 ...]
D[i][k] = min(D[i=1][k] + D[i][k-1], INFINITY);
}
}
unsigned c; // command number
unsigned n; // half length of array
while(in_file >> c >> n) { // Read two numbers first is command second is value
// Our position in DP
unsigned u = n; // Row for DP matrix
unsigned v = n; // Col for DP matrix
// Position in the array
unsigned p = 1; // start index into x array
unsigned q = n + 1; // Halfway index into x array
unsigned m = 2 * n; // Array length
// Which mode are we in?
if(c == 1) {
// Modify array according to K
// file looks like "1 n k"
int k_num;
in_file >> k_num;
// iterate over array in memory
// We have two cursors p to the start of the x array and q to the middle
// We change the x array depending on the special K value
// if K is < the DP cell above us we set the
// at the end we will have a matrix where half the values are overwritten by the index
// e.g. [1000 2000 3000 4000 5000 6000 7000 8000] -> [1 3 4 4000 2 5]
for(int i = 1; i <= m; i++) {
// Check if input_k is < DP value UP in the matrix
if(D[u][v-1] >= k_num) {
// modify first half of array
x[p++]= i; // overwrite with index
v--; // move up
} else {
// modify second half of array
x[q++] = i; // advance the halfway index and set current x value to index
k_num -= D[u--][v-1]; // decrease special value by the UP value in DP matrix then move to DP cell left of us
}
}
// Write out array
for(int i = 1; i <= m; i++) {
out_file << x[i] << ' ';
}
out_file << '\n';
// continue; I replaced this with the else branch to make it clearer
} else {
// Calculate K from input array
// Read in array of unsigned ints
for(int i = 1; i <= m; i++) {
in_file >> x[i];
}
int k_num_2 = 1;
for(int i = 1; v > 0; i++) {
// if index from start == the index
if(x[p] == i) {
v--; // move up dp cell
p++; // advance p index
} else {
// add above DP cell and then move left
k_num_2 += D[--u+1][v-1];
q++; // idk
}
out_file << k_num_2 << '\n';
}
}
}
return 0;
}
12
Upvotes