제출 #234576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234576		wet_water	보물 찾기 (CEOI13_treasure2)	C++14	10 / 100	5 ms	384 KiB

treasure

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include "treasure.h"

#define MOD 1000000009 
#define MAX_N 105
#define f first
#define s second
 
using namespace std;
 
typedef pair<int, int> ii;
typedef pair<ii, int> pii;
 
int mod_pow(int num, int power)
{
    int test;
    for(test = 1; power; power >>= 1)
    {
        if (power & 1)
            test = (test * num) % MOD;
        num = (num * num) % MOD;
    }
 
    return test;
}

void fastscan(int &number) 
{ 
    //variable to indicate sign of input number 
    bool negative = false; 
    register int c; 
  
    number = 0; 
  
    // extract current character from buffer 
    c = getchar(); 
    if (c=='-') 
    { 
        // number is negative 
        negative = true; 
  
        // extract the next character from the buffer 
        c = getchar(); 
    } 
  
    // Keep on extracting characters if they are integers 
    // i.e ASCII Value lies from '0'(48) to '9' (57) 
    for (; (c>47 && c<58); c=getchar()) 
        number = number *10 + c - 48; 
  
    // if scanned input has a negative sign, negate the 
    // value of the input number 
    if (negative) 
        number *= -1; 
} 

bool cmp(pii a, pii b) {
    return (a.f.s < b.f.s);
}

int ar[MAX_N][MAX_N];
int N, M;

void recurse(int R1, int C1, int R2, int C2, int num) {
	if (num == 0) {
		for (int i = R1; i <= R2; i ++) {
			for (int j = C1; j <= C2; j ++) {
				ar[i][j] = 0;
			}
		}

		return;
	} else if (num == (R2 - R1 + 1) * (C2 - C1 + 1)) {
		for (int i = R1; i <= R2; i ++) {
			for (int j = C1; j <= C2; j ++) {
				ar[i][j] = 1;
			}
		}

		return;
	}

	int r_divide = (R1 + R2) / 2;
	int c_divide = (C1 + C2) / 2;

	int b1 = countTreasure(R1 + 1, C1 + 1, r_divide + 1, c_divide + 1);
	int b2 = countTreasure(R1 + 1, c_divide + 2, r_divide + 1, C2 + 1);
	int b3 = countTreasure(r_divide + 2, C1 + 1, R2 + 1, c_divide + 1);

	recurse(R1, C1, r_divide, c_divide, b1);
	recurse(R1, c_divide + 1, r_divide, C2, b2);
	recurse(r_divide + 1, C1, R2, c_divide, b3);
	recurse(r_divide + 1, c_divide + 1, R2, C2, num - b1 - b2 - b3);
}

void findTreasure (int N) {
	int x = countTreasure(1, 1, N, N);
	recurse(0, 0, N - 1, N - 1, x);

	for (int i = 0; i < N; i ++) {
		for (int j = 0; j < N; j ++) {
			if (ar[i][j])
				Report(i + 1, j + 1);
		}
	}	
	
	return;	
}

• Subtask 1: 10 / 100