Submission #72332

#	Time	Username	Problem	Language	Result	Execution time	Memory
72332		cat > /dev/null (#118)	Magic Dowsing (FXCUP3_magic)	C++17	25 / 100	3 ms	380 KiB

dowsing

#include "dowsing.h"
#include<set>
#include<ctime>
#include<cstdio>
#include<cstdlib>
using namespace std;

void FindTreasure(int N) {
    bool t11 = Detect(1, 1), t12 = Detect(1, 2), t21 = Detect(2, 1);

    if (!t11 && t12 && t21) {
        if (Detect(1, 3))
            Report(1, 1);
        else
            Report(2, 2);
        return;
    }
    if (t11 && t12 && !t21) {
        for (int i = 1; i <= N; i ++)
            if (!Detect(1, i)) {
                Report(1,i);
                return;
            }
    }
    if (t11 && t21 && !t12) {
        for (int i = 1; i <= N; i ++)
            if (!Detect(i, 1)) {
                Report(i,1);
                return;
            }
    }

    if (t11 && !t12 && !t21) {
        if (Detect(1, 3)) {
            Report(1, 2);
            return;
        }
        if (Detect(3, 1)) {
            Report(2, 1);
            return;
        }
    }

    srand(time(NULL));
    set<int> rest, rest2;

    for (int i = 1; i <= N; i ++)
        rest.insert(i), rest2.insert(i);

    int row, col;

    while (true) {
        int ra = ((long long)rand() * rand()) % rest.size();

        int val; 
        for (int item : rest) {
            val = item;
            if (!ra)
                break;
            ra--;
        }

        if (Detect(1, val)) {
            col = val;
            break;
        }

        rest.erase(val);
    }


    while (true) {
        int ra = ((long long)rand() * rand()) % rest2.size();

        int val; 
        for (int item : rest2) {
            val = item;
            if (!ra)
                break;
            ra--;
        }

        if (Detect(val,1)) {
            row = val;
            break;
        }

        rest2.erase(val);
    }

    Report(row, col);
    return;
}

• Subtask 1: 25 / 100