//// Treasure.cpp : This file contains the 'main' function. Program execution begins and ends there.
////
//
//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//typedef vector<int> vi;
//typedef vector<vi> vvi;
//typedef vector<vvi> vvvi;
//vvi mat;
//
//void calc(int l1, int l2, int r1, int r2, int x)
//{
// if (x == 0)return;
// if (x == (l2 - l1 + 1) * (r2 - r1 + 1))
// {
// for (int i = l1 - 1; i <= l2 - 1; i++) for (int j = r1 - 1; j <= r2 - 1; j++) mat[i][j] = 1;
// return;
// }
// if (l1 == l2)
// {
// if (r1 == r2)
// {
// mat[l1 - 1][r1 - 1] = x;
// return;
// }
// int a, b;
// int m = (r1 + r2) / 2;
// cout << l1 << " " << r1 << " " << l1 << " " << m << endl;
// cin >> a; b = x - a;
// if (r1 + 1 == r2)
// {
// mat[l1 - 1][r1 - 1] = a;
// mat[l1 - 1][r2 - 1] = b;
// return;
// }
// calc(l1, l2, r1, m, a); calc(l1, l2, m+1, r2, b);
// return;
// }
// if (r1 == r2)
// {
// if (l1 == l2)
// {
// mat[l1 - 1][r1 - 1] = x;
// return;
// }
// int a, b;
// int m = (l1 + l2) / 2;
// cout << l1 << " " << r1 << " " << m << " " << r1 << endl;
// cin >> a; b = x - a;
// if (l1 + 1 == l2)
// {
// mat[l1 - 1][r1 - 1] = a;
// mat[l2 - 1][r1 - 1] = b;
// return;
// }
// calc(l1, m, r1, r2, a); calc(m + 1, l2, r1, r2, b);
// return;
// }
// int ab, dc, ad, bc;
// int ms = (l1 + l2) / 2, mu = (r1 + r2) / 2;
// cout << l1 << " " << r1 << " " << ms << " " << r2 << endl;
// cin >> ab; dc = x - ab;
// cout << l1 << " " << r1 << " " << l2 << " " << mu << endl;
// cin >> ad; bc = x - ad;
// int a, b, c, d;
// cout << l1 << " " << r1 << " " << ms << " " << mu << endl;
// cin >> a;
// d = ad - a;
// b = ab - a;
// c = bc - b;
// if (l1 + 1 == l2 && r1 + 1 == r2)
// {
// mat[l1 - 1][r1-1] = a;
// mat[l1 - 1][r2 - 1] = d;
// mat[l2 - 1][r1 - 1] = b;
// mat[l2 - 1][r2 - 1] = c;
// return;
// }
// calc(l1, ms, r1, mu, a);
// calc(ms + 1, l2, r1, mu, d);
// calc(l1, ms, mu + 1, r2, b);
// calc(ms + 1, l2, mu + 1, r2, c);
//}
//
//int main()
//{
// ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int n; cin >> n;
// mat.resize(n, vi(n, 0));
// cout << 1 << " " << 1 << " " << n << " " << n << endl;
// int a; cin >> a;
// calc(1, n, 1, n, a);
// cout << "END" << endl;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) cout << mat[i][j];
// cout << endl;
// }
//}
#include "treasure.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
vvi mat;
void calc(int l1, int l2, int r1, int r2, int x)
{
if (x == 0)return;
if (x == (l2 - l1 + 1) * (r2 - r1 + 1))
{
for (int i = l1 - 1; i <= l2 - 1; i++) for (int j = r1 - 1; j <= r2 - 1; j++) mat[i][j] = 1;
return;
}
if (l1 == l2)
{
if (r1 == r2)
{
mat[l1 - 1][r1 - 1] = x;
return;
}
int a, b;
int m = (r1 + r2) / 2;
//cout << l1 << " " << r1 << " " << l1 << " " << m << endl;
//cin >> a;
a = countTreasure(l1, r1, l1, m);
b = x - a;
if (r1 + 1 == r2)
{
mat[l1 - 1][r1 - 1] = a;
mat[l1 - 1][r2 - 1] = b;
return;
}
calc(l1, l2, r1, m, a); calc(l1, l2, m + 1, r2, b);
return;
}
if (r1 == r2)
{
if (l1 == l2)
{
mat[l1 - 1][r1 - 1] = x;
return;
}
int a, b;
int m = (l1 + l2) / 2;
//cout << l1 << " " << r1 << " " << m << " " << r1 << endl;
//cin >> a;
a = countTreasure(l1, r1, m, r1); b = x - a;
if (l1 + 1 == l2)
{
mat[l1 - 1][r1 - 1] = a;
mat[l2 - 1][r1 - 1] = b;
return;
}
calc(l1, m, r1, r2, a); calc(m + 1, l2, r1, r2, b);
return;
}
int ab, dc, ad, bc;
int ms = (l1 + l2) / 2, mu = (r1 + r2) / 2;
//cout << l1 << " " << r1 << " " << ms << " " << r2 << endl;
//cin >> ab;
ab = countTreasure(l1, r1, ms, r2); dc = x - ab;
//cout << l1 << " " << r1 << " " << l2 << " " << mu << endl;
//cin >> ad;
ad = countTreasure(l1, r1, l2, mu); bc = x - ad;
int a, b, c, d;
//cout << l1 << " " << r1 << " " << ms << " " << mu << endl;
//cin >> a;
a = countTreasure(l1, r1, ms, mu);
d = ad - a;
b = ab - a;
c = bc - b;
if (l1 + 1 == l2 && r1 + 1 == r2)
{
mat[l1 - 1][r1 - 1] = a;
mat[l1 - 1][r2 - 1] = b;
mat[l2 - 1][r1 - 1] = d;
mat[l2 - 1][r2 - 1] = c;
return;
}
calc(l1, ms, r1, mu, a);
calc(ms + 1, l2, r1, mu, d);
calc(l1, ms, mu + 1, r2, b);
calc(ms + 1, l2, mu + 1, r2, c);
}
void findTreasure(int n) {
//int cnt = countTreasure(1, 1, N, N);
//if(cnt > 0) Report (1, 1);
mat.resize(n, vi(n, 0));
//cout << 1 << " " << 1 << " " << n << " " << n << endl;
int a = countTreasure(1, 1, n, n);
calc(1, n, 1, n, a);
//cout << "END" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) if (mat[i][j] == 1) Report(i + 1, j + 1);
//cout << endl;
}
}
Compilation message
treasure.cpp: In function 'void calc(int, int, int, int, int)':
treasure.cpp:163:13: warning: variable 'dc' set but not used [-Wunused-but-set-variable]
163 | int ab, dc, ad, bc;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
0 ms |
212 KB |
Output is partially correct - N = 5, K = 461, score = 8 |
2 |
Partially correct |
0 ms |
212 KB |
Output is partially correct - N = 10, K = 7625, score = 1 |
3 |
Correct |
0 ms |
212 KB |
Output is correct - N = 15, K = 19256, score = 10 |
4 |
Correct |
1 ms |
212 KB |
Output is correct - N = 16, K = 20684, score = 10 |
5 |
Partially correct |
1 ms |
340 KB |
Output is partially correct - N = 55, K = 7853668, score = 1 |
6 |
Partially correct |
1 ms |
340 KB |
Output is partially correct - N = 66, K = 17020013, score = 1 |
7 |
Correct |
1 ms |
340 KB |
Output is correct - N = 77, K = 6869342, score = 10 |
8 |
Correct |
1 ms |
340 KB |
Output is correct - N = 88, K = 9049947, score = 10 |
9 |
Partially correct |
1 ms |
340 KB |
Output is partially correct - N = 99, K = 80917816, score = 1 |
10 |
Partially correct |
1 ms |
340 KB |
Output is partially correct - N = 100, K = 85220635, score = 1 |