Submission #635922

#	Time	Username	Problem	Language	Result	Execution time	Memory
635922		ygim	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	53 / 100	1 ms	340 KiB

treasure

//// 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 (stderr)

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;
      |             ^~

• Subtask 1: 53 / 100