OJ Board

Code: Select all

#include <cstdlib>
#include <string>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <stack>
#include <cctype>
#include <queue>

using namespace std;

class Node {

public:
	int nr, nl, c;
	Node * right, * left;
	Node () : right (0), left (0), nr(0), nl(0), c(0) {}
};

void fill_tree (Node* tree, int B, int A = 1) {

	if (A >= B) return;

	Node* n1 = new Node();
	n1->nl = A, n1->nr = (A + B) / 2, n1->c = n1->nr - n1->nl + 1;
	tree->left = n1;
	if (A < B) fill_tree (tree->left, (A + B) / 2, A);

	Node* n2 = new Node();
	n2->nl = (A + B) / 2 + 1, n2->nr = B, n2->c = n2->nr - n2->nl + 1;
	tree->right = n2;
	if (A < B) fill_tree (tree->right, B, (A + B) / 2 + 1);
}

int delete_position (Node* tree, int pos) {

	--tree->c;

	if (tree->nl == tree->nr)
		return tree->nl;
	
	if (pos <= tree->left->c)
		return delete_position (tree->left, pos);

	else 
		return delete_position (tree->right, pos - tree->left->c);
}

int main() {

	int T, K, N;

	scanf ("%d", &T);

	for (int t = 0; t < T; ++t) {

		Node* tree = new Node();
		scanf ("%d %d", &N, &K);

		tree->nr = 1, tree->nl = N, tree->c = K;
		fill_tree (tree, N);

		int j = 0;

		while (N > 1) {
			j = (j + K - 1) % N--;
			delete_position (tree, j + 1);
		}

		printf("Case %d: %d\n", 1 + t, delete_position (tree, 1));
	}
}