Submission #988822

#	Time	Username	Problem	Language	Result	Execution time	Memory
988822		benjaminkleyn	산악 구조대 (JOI13_mountain)	C++17	0 / 100	4 ms	860 KiB

mountain

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

int x;

map<pair<int,int>,int> m;

bool in_bounds(pair<int,int> p, int R, int C){
    return (p.first>0&&p.second>0&&p.first<=R&&p.second<=C);
}

bool check(pair<int,int> p){
    int sus;
    if(m.count(p))sus=m[p];
    else sus=Measure(p.first,p.second);
    // cout << p.first << ' ' << p.second << ' ' << sus << '\n';
    if (sus == x)Pinpoint(p.first,p.second);

    if(sus<x)return 0;
    else return 1;
}
    
int binary_search(vector<pair<int,int>>& a){
    int lo=0,hi=a.size()-1;

    while(lo<hi){
        int mid=(lo+hi+1)/2;
        if(check(a[mid]))lo=mid;
        else hi=mid-1;
    }
    check(a[lo]);
    return lo;
}
    

void Rescue(int R, int C, int rp, int cp, int X) {

    x=X;

    check({rp,cp});

    // for (int r = 1; r <= R; r++) {
    //     for (int c = 1; c <= C; c++) {
    //         if (Measure(r, c) == X) {
    //             Pinpoint(r, c);
    //         }
    //     }
    // }

    

    vector<pair<int,int>> sus;

    //up and right
    for(int tr=rp,tc=cp;in_bounds({tr,cp},R,C);tr--,tc++)sus.push_back({tr,tc});
    // cout << "sus";
    // for(pair<int,int> p : sus)cout << '(' << p.first << ' ' << p.second << ')';
    // cout << '\n';

    if(!sus.empty()&&check(sus[0])){
        int index=binary_search(sus);

        int r=sus[index].first,c=sus[index].second;
        vector<pair<int,int>> a,b;

        for(int tr=r,tc=c;in_bounds({tr,tc},R,C);tr--)a.push_back({tr,tc});
        if(!a.empty()&&check(a[0]))binary_search(a);

        for(int tr=r,tc=c;in_bounds({tr,tc},R,C);tc++)b.push_back({tr,tc});
        if(!b.empty()&&check(b[0]))binary_search(b);

        // cout << "a";
        // for(pair<int,int> p : a)cout << '(' << p.first << ' ' << p.second << ')';
        // cout << '\n';
        // cout << "b";
        // for(pair<int,int> p : b)cout << '(' << p.first << ' ' << p.second << ')';
        // cout << '\n';
    }

    //right and down
    sus.clear();
    for(int tr=rp,tc=cp;in_bounds({tr,cp},R,C);tr++,tc++)sus.push_back({tr,tc});
    // cout << "sus";
    // for(pair<int,int> p : sus)cout << '(' << p.first << ' ' << p.second << ')';
    // cout << '\n';

    if(!sus.empty()&&check(sus[0])){
        int index=binary_search(sus);

        int r=sus[index].first,c=sus[index].second;
        vector<pair<int,int>> a,b;

        for(int tr=r,tc=c;in_bounds({tr,tc},R,C);tr++)a.push_back({tr,tc});
        if(!a.empty()&&check(a[0]))binary_search(a);

        for(int tr=r,tc=c;in_bounds({tr,tc},R,C);tc++)b.push_back({tr,tc});
        if(!b.empty()&&check(b[0]))binary_search(b);

        // cout << "a";
        // for(pair<int,int> p : a)cout << '(' << p.first << ' ' << p.second << ')';
        // cout << '\n';
        // cout << "b";
        // for(pair<int,int> p : b)cout << '(' << p.first << ' ' << p.second << ')';
        // cout << '\n';
    }

    //left and down
    sus.clear();
    for(int tr=rp,tc=cp;in_bounds({tr,cp},R,C);tr++,tc--)sus.push_back({tr,tc});
    // cout << "sus";
    // for(pair<int,int> p : sus)cout << '(' << p.first << ' ' << p.second << ')';
    // cout << '\n';

    if(!sus.empty()&&check(sus[0])){
        int index=binary_search(sus);

        int r=sus[index].first,c=sus[index].second;
        vector<pair<int,int>> a,b;

        for(int tr=r,tc=c;in_bounds({tr,tc},R,C);tr++)a.push_back({tr,tc});
        if(!a.empty()&&check(a[0]))binary_search(a);

        for(int tr=r,tc=c;in_bounds({tr,tc},R,C);tc--)b.push_back({tr,tc});
        if(!b.empty()&&check(b[0]))binary_search(b);

        // cout << "a";
        // for(pair<int,int> p : a)cout << '(' << p.first << ' ' << p.second << ')';
        // cout << '\n';
        // cout << "b";
        // for(pair<int,int> p : b)cout << '(' << p.first << ' ' << p.second << ')';
        // cout << '\n';
    }

    //up and left
    sus.clear();
    for(int tr=rp,tc=cp;in_bounds({tr,cp},R,C);tr--,tc--)sus.push_back({tr,tc});
    // cout << "sus";
    // for(pair<int,int> p : sus)cout << '(' << p.first << ' ' << p.second << ')';
    // cout << '\n';

    if(!sus.empty()&&check(sus[0])){
        int index=binary_search(sus);

        int r=sus[index].first,c=sus[index].second;
        vector<pair<int,int>> a,b;

        for(int tr=r,tc=c;in_bounds({tr,tc},R,C);tr--)a.push_back({tr,tc});
        if(!a.empty()&&check(a[0]))binary_search(a);

        for(int tr=r,tc=c;in_bounds({tr,tc},R,C);tc--)b.push_back({tr,tc});
        if(!b.empty()&&check(b[0]))binary_search(b);

        // cout << "a";
        // for(pair<int,int> p : a)cout << '(' << p.first << ' ' << p.second << ')';
        // cout << '\n';
        // cout << "b";
        // for(pair<int,int> p : b)cout << '(' << p.first << ' ' << p.second << ')';
        // cout << '\n';
    }


}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80