Submission #24925

#	Time	Username	Problem	Language	Result	Execution time	Memory
24925		tlwpdus	산악 구조대 (JOI13_mountain)	C++14	100 / 100	18 ms	640 KiB

mountain

    #include "grader.h"
    #include <bits/stdc++.h>
     
    using namespace std;
     
    int x, n, m;
    int ax, ay;
    int rcnt = 0;
     
    void rrot(int &x, int &y, int cnt) {
        int i;
        for (i=cnt;i<4;i++) {
            int tx = y, ty = ((i&1)?m:n)+1-x;
            x = tx; y = ty;
        }
    }
     
    bool dnc(int sx, int sy, int ex, int ey) {
        if (sx>ex||sy>ey) return false;
        int mx = (sx+ex)>>1;
        int s = sy, e = ey, tx, ty;
        while(s<=e) {
            int m = (s+e)>>1;
            tx = mx, ty = m;
            rrot(tx,ty,rcnt);
            int val = Measure(tx,ty);
     
            if (val<x) e = m-1;
            else if (val>x) s = m+1;
            else break;
        }
        if (s<=e) {
            ax = mx; ay = (s+e)>>1;
            return true;
        }
        return dnc(sx,s,mx-1,ey)||dnc(mx+1,sy,ex,e);
    }
     
    void Rescue(int R, int C, int RS, int CS, int X) {
        n=R; m=C; x=X;
        if (Measure(RS,CS)==X) {
            Pinpoint(RS,CS);
            return;
        }
        for (rcnt=0;rcnt<4;rcnt++) {
            bool flag = dnc(RS+1,CS+1,((rcnt&1)?m:n),((rcnt&1)?n:m));
            if (flag) {
                rrot(ax,ay,rcnt);
                Pinpoint(ax,ay);
                return;
            }
            flag = dnc(RS+1,CS,((rcnt&1)?m:n),CS);
            if (flag) {
                rrot(ax,ay,rcnt);
                Pinpoint(ax,ay);
                return;
            }
            int &x = RS, &y = CS;
            int tx = y, ty = ((rcnt&1)?m:n)+1-x;
            x = tx; y = ty;
        }
    }

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