Submission #40576

#	Time	Username	Problem	Language	Result	Execution time	Memory
40576		baactree	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	0 / 100	2 ms	676 KiB

treasure

#include "treasure.h"
#include <string.h>
#include <stdio.h>
int tree[105];
int col[105];
int mat[105][105];
int n, m;
int calc(int r1, int c1, int r2, int c2) {
	if (r1 == 1) {
		if (c2 - c1 + 1 > c1-1)
			return countTreasure(r1, c1, n, n);
		return m - countTreasure(1, 1, n, c1-1);
	}
	return countTreasure(r1, c1, r2, c2);
}
void update(int idx, int val) {
	idx = 105 - idx;
	while (idx < 105) {
		tree[idx] += val;
		idx += idx&(-idx);
	}
}
int query(int idx) {
	int ret = 0;
	idx = 105 - idx;
	while (idx) {
		ret += tree[idx];
		idx -= idx&(-idx);
	}
	return ret;
}
void solve_col(int le, int ri, int cnt) {
	if (!cnt)
		return;
	if (le == ri) {
		col[le] = cnt;
		update(le, cnt);
		return;
	}
	int mid = (le + ri) / 2;
	int right = calc(1, mid + 1, n, n) - query(ri);
	int left = cnt - right;
	solve_col(mid + 1, ri, right);
	solve_col(le, mid, left);
}
void solve_row(int le, int ri, int cnt,int col) {
	if (!cnt)
		return;
	if (le == ri) {
		mat[le][col] = 1;
		update(le, cnt);
		return;
	}
	int mid = (le + ri) / 2;
	int right = calc(mid + 1, col, n, n) - query(ri);
	int left = cnt - right;
	solve_row(mid + 1, ri, right, col);
	solve_row(le, mid, left, col);
}
void findTreasure (int N) {
	n = N;
	m = countTreasure(1, 1, n, n);
	solve_col(1, n, m);
	memset(tree, 0, sizeof(tree));
	for (int i = n; i >= 1; i--) 
		solve_row(1, n, col[i],i);
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= n; j++) 
			if (mat[i][j])
				Report(i, j);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:63:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         my_assert(strlen(A[i]+1) == N, "each line of the map must contain N zeroes or ones (before loop)");
                                  ^

• Subtask 1: 0 / 100