oj.uz

Submission #40589

# Submission time Handle Problem Language Result Execution time Memory
40589 2018-02-05T07:50:50 Z baactree Treasure (different grader from official contest) (CEOI13_treasure2) C++14
0 / 100
 2 ms 684 KB 
#include "treasure.h"
#include <string.h>
#include <stdio.h>
int tree[105];
int col[105];
int mat[105][105];
int n, m;
bool flip;
int calc(int r1, int c1, int r2, int c2) {
	int ret = 0;
	if (r1 == 1) {
		if (c2 - c1 + 1 > c1-1)
			ret=countTreasure(r1, c1, n, n);
		else
			ret=m - countTreasure(1, 1, n, c1-1);
	}
	else {

		ret=countTreasure(r1, c1, r2, c2);
	}
	if (flip)
		ret = (r2 - r1 + 1)*(c2 - c1 + 1) - ret;
	return ret;
}
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) {
	memset(tree, 0, sizeof(tree));
	memset(mat, 0, sizeof(mat));
	memset(col, 0, sizeof(col));
	n = N;
	m = countTreasure(1, 1, n, n);
	if (m > n*n / 2) 
		flip = true;
	solve_col(1, n, n*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 (flip && !mat[i][j])
				Report(i, j);
			if(!flip&&mat[i][j])
				Report(i, j);
		}
}

Compilation message

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Invalid Access
2 Incorrect 1 ms 376 KB Invalid Access
3 Incorrect 1 ms 428 KB Invalid Access
4 Incorrect 1 ms 500 KB Invalid Access
5 Incorrect 2 ms 632 KB Invalid Access
6 Incorrect 1 ms 684 KB Invalid Access
7 Incorrect 1 ms 684 KB Invalid Access
8 Incorrect 1 ms 684 KB Invalid Access
9 Incorrect 2 ms 684 KB Invalid Access
10 Incorrect 2 ms 684 KB Invalid Access