oj.uz

Submission #284190

# Submission time Handle Problem Language Result Execution time Memory
284190 2020-08-27T01:48:08 Z FlashGamezzz Treasure (different grader from official contest) (CEOI13_treasure2) C++17
60 / 100
 1 ms 512 KB 
#include "treasure.h"
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>

using namespace std;
 
int psums[101][101] = {}, ul[101][101] = {}, dr[101][101] = {};

int zero(int a1, int a2, int d){
	if (a1 == 2 || a2 == 2){
    	return 1;
    }
    if (a1 == 0 || a2 == 0){
    	return 0;
    }
    if (d > 2){
    	return 0;
    }
    return 1;
}
void findTreasure (int N) {
	int h = N/2;
    if (N % 2 != 0){
    	h++;
    }
	for (int r = 1; r <= N; r++){
		for (int c = 1; c <= N; c++){
			bool a = (r > h), b = (c > h);
			if (a && b){
				psums[r][c] = countTreasure(1, 1, r, c);
			} else {
				if (a && c > 1){
					dr[r][c] = countTreasure(1, c, r, N);
				}
				if (b && r > 1){
					ul[r][c] = countTreasure(r, 1, N, c);
				}
			}
		}
	}
	for (int i = N; i > h; i--){
		ul[1][i] = psums[N][i];
		dr[i][1] = psums[i][N];
	}
	for (int r = N; r > h; r--){
		for (int c = 1; c < h; c++){
			psums[r][c] = psums[r][N]-dr[r][c+1];
		}
		psums[r][h] = countTreasure(1, 1, r, h);
	}
	for (int c = N; c > h; c--){
		for (int r = 1; r < h; r++){
			psums[r][c] = psums[N][c]-ul[r+1][c];
		}
		psums[h][c] = countTreasure(1, 1, h, c);
	}
	for (int r = h; r >= 1; r--){
		for (int c = h; c >= 1; c--){
        	if (r % 2 != 0 && c == 1){
            	continue;
			}
            if (c % 2 != 0 && r == 1){
            	continue;
			}
            psums[r][c] = countTreasure(r+1, c+1, N, N)-psums[N][N]+psums[N][c]+psums[r][N];
		}
	}
    for (int i = 1; i <= h; i+=2){
   		psums[i][1] = psums[i-1][1] + zero(psums[i][2]-psums[i-1][2], psums[i+1][1]-psums[i-1][1], psums[i+1][2]-psums[i-1][2]);
        psums[1][i] = psums[1][i-1] + zero(psums[2][i]-psums[2][i-1], psums[1][i+1]-psums[1][i-1], psums[2][i+1]-psums[2][i-1]);
    }
	for (int r = 1; r <= N; r++){
		for (int c = 1; c <= N; c++){
			if (psums[r][c] == psums[r-1][c]+psums[r][c-1]-psums[r-1][c-1]+1){
				Report(r, c);
			}
		}
	}
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct - N = 5, K = 262, score = 10
2 Correct 0 ms 384 KB Output is correct - N = 10, K = 4267, score = 10
3 Correct 1 ms 384 KB Output is correct - N = 15, K = 21912, score = 10
4 Correct 0 ms 384 KB Output is correct - N = 16, K = 28344, score = 10
5 Incorrect 1 ms 384 KB Error - no treasure at (r, c) : r = 1, c = 15
6 Incorrect 1 ms 384 KB Error - no treasure at (r, c) : r = 1, c = 33
7 Correct 1 ms 384 KB Output is correct - N = 77, K = 15323842, score = 10
8 Correct 1 ms 512 KB Output is correct - N = 88, K = 26156460, score = 10
9 Incorrect 1 ms 384 KB Error - no treasure at (r, c) : r = 1, c = 17
10 Incorrect 1 ms 384 KB Error - no treasure at (r, c) : r = 1, c = 11