토너먼트 노멀 케이스 (n != 2^k)

checkcheck.cpp

#include <iostream>

#include <fstream>

using namespace std;

int n, m, size;

int tree[1000];

int player[1000];

double Log2( double n )  

{  

    // log(n)/log(2) is log2.  

    return log( n ) / log( 2.0 );  

}

void doBin(int input)

{

int head = 1;

int s = pow(2.0, (ceil(Log2(n) + 0.5) - 1));

int offset = s + s - 1;

int LowExt = 2 * ((n - 1) - (s - 1));

while(head < n) // 찾아가기

{

if(head * 2 >= n)

break;

//if(player[tree[head * 2]] >= player[tree[head * 2 + 1]]) // 왼쪽이 더 크면

if(player[tree[head * 2]] >= input) // 왼쪽이 더 크면

{

head *= 2;

}

else

{

head = head * 2 + 1;

}

}

if(head * 2 > offset) // 최하단 레벨

{

if(player[head * 2 - (offset)] >= input) // 왼쪽이 더 크면

{

player[head * 2 - (offset)] -= input;

//tree[head] = head * 2 - (n - 1); // 왼쪽이 새엄마

}

else

{

player[head * 2 - (offset) + 1] -= input;

//tree[head] = head * 2 - (n - 1) + 1; // 오른쪽이 새엄마

}

// 리프노드 처리

if(player[head * 2 - (offset)] >= player[head * 2 - (offset) + 1]) // 왼쪽이 더 크면

{

tree[head] = head * 2 - (offset); // 왼쪽이 새엄마

}

else

{

tree[head] = head * 2 - (offset) + 1; // 오른쪽이 새엄마

}

}

else // 최하단 레벨 + 1 // k > LowExt

{

if(player[head * 2 - (n - 1) + LowExt] >= input) // 왼쪽이 더 크면

{

player[head * 2 - (n - 1) + LowExt] -= input;

//tree[head] = head * 2 - (n - 1); // 왼쪽이 새엄마

}

else

{

player[head * 2 - (n - 1) + 1 + LowExt] -= input;

//tree[head] = head * 2 - (n - 1) + 1; // 오른쪽이 새엄마

}

// 리프노드 처리

if(player[head * 2 - (n - 1) + LowExt] >= player[head * 2 - (n - 1) + LowExt + 1]) // 왼쪽이 더 크면

{

tree[head] = head * 2 - (n - 1) + LowExt; // 왼쪽이 새엄마

}

else

{

tree[head] = head * 2 - (n - 1) + LowExt + 1; // 오른쪽이 새엄마

}

}

if((n % 2 == 1) && head / 2 == (s - 1 + LowExt / 2) / 2) // 혼재된 구간

{

head = head / 2;

if(player[tree[head * 2]] >= player[head * 2 - (n - 1) + LowExt + 1]) // 왼쪽이 더 크면

{

tree[head] = tree[head * 2]; // 왼쪽이 새엄마

}

else

{

tree[head] = head * 2 - (n - 1) + LowExt + 1; // 오른쪽이 새엄마

}

}

head = head / 2;

while(head > 0) // 트리 올라가면서 복구

{

if(player[tree[head * 2]] >= player[tree[head * 2 + 1]]) // 왼쪽이 더 크면

{

tree[head] = tree[head * 2]; // 왼쪽이 새엄마

}

else

{

tree[head] = tree[head * 2 + 1]; // 오른쪽이 새엄마

}

head = head / 2;

}

for(int i = 1; i <= n; i ++)

{

cout << player[i] << " ";

}

cout << endl;

}

void init()

{

int p = -1;

int s = pow(2.0, (ceil(Log2(n) + 0.5) - 1));

int offset = s + s - 1;

int LowExt = 2 * ((n - 1) - (s - 1));

if (n % 2 == 0)

{

 for (int k=1; k<=n; k=k+2) {  

if(k <= LowExt)

{

p = (k +offset)/2;

}

else

{

p = (k - LowExt + n -1)/2;

}

 tree[p] = k; 

 }

}

else { // n 이 홀수

for (int k = 1; k <= LowExt; k=k+2)

{ 

p = (k + offset) / 2;

tree[p] = k;

}

for(int k = LowExt  + 2; k <= n; k=k+2 )

{ 

p = (k  - LowExt + n - 1) / 2; 

tree[p] = k;

}

}

for (int k = (n-1)/2; k > 0; k--) 

tree[k] = tree[k * 2];

}

int main()

{

fstream fin("input.txt");

fin >> n >> m >> size;

for(int i = 1; i <= n; i ++)

{

player[i] = size;

}

init();

for(int i = 0; i < m; i ++)

{

int input;

fin >> input;

doBin(input);

}

for(int i = 1; i <= n; i ++)

{

cout << player[i] << " ";

}

cout << endl;

return 0;

}