oj.uz

Submission #116325

# Submission time Handle Problem Language Result Execution time Memory
116325 2019-06-12T08:40:10 Z emilem Treasure (different grader from official contest) (CEOI13_treasure2) C++14
80 / 100
 15 ms 1168 KB 
#include "treasure.h"
#include <iostream>
#include <vector>
#include <map>
#include <tuple>
typedef std::tuple<int, int, int, int> Arguments;
static int n = 0;
int CountTreasures(int minI, int maxI, int minJ, int maxJ)
{
	if (minI < 0 || minJ < 0 || maxI >= n || maxJ >= n)
		return 0;
	static std::map<Arguments, int> cache;
	Arguments curArguments(minI, maxI, minJ, maxJ);
	if (cache.find(curArguments) != cache.end())
		return cache.at(curArguments);
	int ans = countTreasure(minI + 1, minJ + 1, maxI + 1, maxJ + 1);
	cache.insert(std::make_pair(curArguments, ans));
	return ans;
}
inline int CountTreasures(const Arguments& arg)
{
	return CountTreasures(std::get<0>(arg), std::get<1>(arg), std::get<2>(arg), std::get<3>(arg));
}
Arguments make_Arguments(const std::pair<int, int>& IArguments, const std::pair<int, int>& JArguments)
{
	return Arguments(IArguments.first, IArguments.second, JArguments.first, JArguments.second);
}

void findTreasure(int N)
{
	n = N;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
		{
			int iDir, jDir;
			iDir = (i + 1 >= n - i) ? -1 : 1;
			jDir = (j + 1 >= n - j) ? -1 : 1;
			std::pair<int, int> iArg, iLessArg, jArg, jLessArg;
			if (iDir == -1) { iArg = std::make_pair(0, i); iLessArg = std::make_pair(0, i - 1); }
			else { iArg = std::make_pair(i, n - 1); iLessArg = std::make_pair(i + 1, n - 1); }
			if (jDir == -1) {jArg = std::make_pair(0, j); jLessArg = std::make_pair(0, j - 1); }
			else {jArg = std::make_pair(j, n - 1); jLessArg = std::make_pair(j + 1, n - 1); }
			int count = CountTreasures(make_Arguments(iArg, jArg)) -
				CountTreasures(make_Arguments(iLessArg, jArg)) - CountTreasures(make_Arguments(iArg, jLessArg)) +
				CountTreasures(make_Arguments(iLessArg, jLessArg));
		}
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
		{
			int iDir, jDir;
			iDir = (i + 1 >= n - i) ? -1 : 1;
			jDir = (j + 1 >= n - j) ? -1 : 1;
			std::pair<int, int> iArg, iLessArg, jArg, jLessArg;
			if (iDir == -1) { iArg = std::make_pair(0, i); iLessArg = std::make_pair(0, i - 1); }
			else { iArg = std::make_pair(i, n - 1); iLessArg = std::make_pair(i + 1, n - 1); }
			if (jDir == -1) {jArg = std::make_pair(0, j); jLessArg = std::make_pair(0, j - 1); }
			else {jArg = std::make_pair(j, n - 1); jLessArg = std::make_pair(j + 1, n - 1); }
			int count = CountTreasures(make_Arguments(iArg, jArg)) -
				CountTreasures(make_Arguments(iLessArg, jArg)) - CountTreasures(make_Arguments(iArg, jLessArg)) +
				CountTreasures(make_Arguments(iLessArg, jLessArg));
			if (count)
				Report(i + 1, j + 1);
		}
}

Compilation message

treasure.cpp: In function 'void findTreasure(int)':
treasure.cpp:43:8: warning: unused variable 'count' [-Wunused-variable]
    int count = CountTreasures(make_Arguments(iArg, jArg)) -
        ^~~~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 384 KB Output is partially correct - N = 5, K = 495, score = 8
2 Partially correct 2 ms 384 KB Output is partially correct - N = 10, K = 5821, score = 8
3 Partially correct 3 ms 384 KB Output is partially correct - N = 15, K = 26880, score = 8
4 Partially correct 2 ms 384 KB Output is partially correct - N = 16, K = 34273, score = 8
5 Partially correct 6 ms 512 KB Output is partially correct - N = 55, K = 4217920, score = 8
6 Partially correct 8 ms 768 KB Output is partially correct - N = 66, K = 8668573, score = 8
7 Partially correct 12 ms 768 KB Output is partially correct - N = 77, K = 15962895, score = 8
8 Partially correct 12 ms 896 KB Output is partially correct - N = 88, K = 27102241, score = 8
9 Partially correct 15 ms 1168 KB Output is partially correct - N = 99, K = 43260000, score = 8
10 Partially correct 14 ms 1024 KB Output is partially correct - N = 100, K = 45017701, score = 8