제출 #1154586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154586		jmuzhen	Aliens (IOI07_aliens)	C++20	20 / 100	0 ms	416 KiB

aliens

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

#define int long long

int N;

#define cerr if (false) cout

using ii = pair<int, int>;

map<ii, bool> mp;

enum Direction
{
    UP, DOWN, LEFT, RIGHT
};

ii getDirection(const Direction d) {
    switch (d) {
    case UP:
        return {0, 1};
    case DOWN:
        return {0, -1};
    case LEFT:
        return {-1, 0};
    case RIGHT:
        return {1, 0};
    default: return {0, 0};
    }
}

struct Point
{
    int x,y;
    Point operator+ (const ii d) const {
        return {x+d.first, y+d.second};
    }
    Point operator+ (const Direction d) const {
        return *this+getDirection(d);
    }
};

void cerrP(const Point p, string msg) {
    cerr << msg << " " << p.x << " " << p.y << endl;
}

bool query(const Point p) {
    if (mp.count(ii{p.x, p.y})) {
        return mp[ii{p.x, p.y}];
    }

    cout << "examine " << p.x << " " << p.y << endl;
    string s; cin >> s;
    bool b = (s == "true");
    cerr << "queryresponse" << b << endl;
    mp[ii{p.x, p.y}] = b;
    return b;
}

enum CornerDirection
{
    TOP_LEFT, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_RIGHT
};

enum Diagonal
{
    DIAGONAL_LEFT, DIAGONAL_RIGHT
};

Diagonal getDiagonalFromCornerDirection(CornerDirection cd) {
    switch (cd) {
    case TOP_LEFT:
        return DIAGONAL_LEFT;
    case TOP_RIGHT:
        return DIAGONAL_RIGHT;
    case BOTTOM_LEFT:
        return DIAGONAL_RIGHT;
    case BOTTOM_RIGHT:
        return DIAGONAL_LEFT;
    }
    assert(false);
}

struct Corner
{
    Point p;
    Diagonal di;
    bool isActuallyCenter = false; // kill myself this is ugly
    Corner(Point p, Diagonal di) {
        this->p = p;
        this->di = di;
    }
    Corner(Point p, CornerDirection cd) {
        this->p = p;
        this->di = getDiagonalFromCornerDirection(cd);
    }
    Corner(Point p, bool b) {
        assert(b);
        this->p = p;
        this->isActuallyCenter = b;
    }
};

CornerDirection getCornerDirection(vector<int> q) {
    if (q[UP] && q[LEFT]) return BOTTOM_RIGHT;
    if (q[UP] && q[RIGHT]) return BOTTOM_LEFT;
    if (q[DOWN] && q[LEFT]) return TOP_RIGHT;
    if (q[DOWN] && q[RIGHT]) return TOP_LEFT;
    assert(false);
}

int binarySearchGetMid(int l, int r) {
    if (l >= 0) return (l+r)/2;
    else {
        return (l+r-1)/2;
    }
}

Point binarySearchGetPointHelper(int fixed_x, int fixed_y, int m) {
    if (fixed_x != -1) return {fixed_x, m};
    if (fixed_y != -1) return {m, fixed_y};
    assert(false);
}

// this function asserts that l is confirmed to be an answer, as is_l_true is always true
int binarySearchHelper(int fixed_x, int fixed_y, int l, int r, bool is_l_true) {
    int ans = 0;
    while (l <= r) {
        int m = binarySearchGetMid(l, r);
        Point p = binarySearchGetPointHelper(fixed_x, fixed_y, m);
        bool R = query(p);
        // depending on is_l_true, increase or decrease
        if (R) {
            ans = m;
            if (is_l_true) {
                // we can move to the right
                l = m+1;
            }
            else {
                // move to the left
                r = m-1;
            }
        }
        else {
            // inverse
            if (is_l_true) {
                r = m-1;
            }
            else {
                l = m+1;
            }
        }
    }
    return ans;
}

enum Side {
    SIDE_UP, SIDE_LEFT, SIDE_RIGHT, SIDE_DOWN
};

Side getSide(vector<int> q) {
    if (!q[RIGHT]) return SIDE_RIGHT;
    if (!q[LEFT]) return SIDE_LEFT;
    if (!q[UP]) return SIDE_UP;
    if (!q[DOWN]) return SIDE_DOWN;
    assert(false);
}

CornerDirection getCornerDirection(Side s) {
    if (s == SIDE_RIGHT) return TOP_RIGHT;
    if (s == SIDE_LEFT) return TOP_LEFT;
    if (s == SIDE_UP) return TOP_RIGHT;
    if (s == SIDE_DOWN) return BOTTOM_RIGHT;
}

// offset is how much we go to the right.
Point diagonallyOffset(Point p, Diagonal di, int offset) {
    if (di == DIAGONAL_LEFT) {
        // looks like \
        // increase x. decrease y
        return {p.x+offset, p.y-offset};
    }
    else {
        return {p.x+offset, p.y+offset};
    }
}

// l, r represent the min and max offset we can use. can be negative.
Point binarySearchDiagonalHelper(Point p, int l, int r, Diagonal di) {
    // l, r must be same sign
    assert(l*r>=0);
    Point ans;
    while (l <= r) {
        int m = binarySearchGetMid(l, r);
        Point newp = diagonallyOffset(p, di, m);
        bool R = query(newp);
        if (R) {
            ans = newp;
            // we can decrease offset if it's negative, or increase if it's positive
            if (m < 0) {
                // move to the left
                r = m-1;
            }
            else {
                l = m+1;
            }
        }
        else {
            // move to the right
            // inverse
            if (m < 0) {
                l = m+1;
            }
            else {
                r = m-1;
            }
        }
    }
    return ans;
}

Point binarySearchMidpointDiagonal(Point p, Diagonal di) {
    // do both left and right side
    int l1 = -min(p.x - 1, p.y - 1), r1 = 0;
    int l2 = 0, r2 = min(N - p.x, N - p.y);
    cerrP(p, "diagonalp");
    cerrP({l1,r1}, "diagonallr1");
    cerrP({l2,r2}, "diagonallr2");
    Point p1 = binarySearchDiagonalHelper(p, l1, r1, di);
    Point p2 = binarySearchDiagonalHelper(p, l2, r2, di);

    // take midpoint
    return {(p1.x+p2.x)/2, (p1.y+p2.y)/2};
}


Corner getRegionalCorner(Point p) {
    auto [x,y] = p;
    vector<int> _queries = {query(p+UP), query(p+DOWN), query(p+LEFT), query(p+RIGHT)};
    int sum = accumulate(_queries.begin(), _queries.end(), 0LL);
    assert(sum>=2);
    if (sum == 4) {
        // we are at the center, observe that we can just return this point along with any diagonal direction
        /// SOMEHOW CHANGING THIS FROM LEFT TO RIGHT GAVE ME +10 KILL MYSELF
        return Corner{p, true};
    }
    if (sum == 2) {
        // we are at a corner already
        // find diagonal direction
        return Corner{p, getCornerDirection(_queries)};
    }
    if (sum == 3) {
        // we are at a side
        // binary search depending on what side we are
        Side side = getSide(_queries);
        int bsl, bsr;
        int fixed_x = -1, fixed_y = -1;
        if (side == SIDE_UP || side == SIDE_DOWN) {
            bsl = x, bsr = N;
            fixed_y = y;
        }
        else {
            bsl = y, bsr = N;
            fixed_x = x;
        }

        int var = binarySearchHelper(fixed_x, fixed_y, bsl, bsr, true);
        Point c;
        if (fixed_x != -1) c = {fixed_x, var};
        else c = {var, fixed_y};

        return {c, getCornerDirection(side)};
    }
}

void output(const Point p) {
    cout << "solution " << p.x << " " << p.y << endl;
}

signed main() {
    Point p;
    cin >> N >> p.x >> p.y;

    // get regional corner first
    Corner rc = getRegionalCorner(p);
    cerrP(rc.p, "regional corner");

    Point rcenter;
    if (rc.isActuallyCenter) rcenter = rc.p; 
    // then get the diagonal midpoint (regional center)
    else {
        Point rcenter = binarySearchMidpointDiagonal(rc.p, rc.di);
    }
    
    // find the midpoint of current rcenter's diagonal (any one of them)
    // Diagonal otherdi = (Diagonal)(1 - rc.di);
    Point rcenter_diag_mp = binarySearchMidpointDiagonal(rcenter, DIAGONAL_LEFT);

    //
    // if (rcenter_diag_mp.x == rcenter.x && rcenter_diag_mp.y == rcenter.y) {
    //     cerr << "answer found, is just rcenter" << endl;
    //     output(rcenter);
    //     return 0;
    // }

    // now find the midpoint of the other diagonal, that's the answer.
    Point gcenter = binarySearchMidpointDiagonal(rcenter_diag_mp, DIAGONAL_RIGHT);
    output(gcenter);

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'CornerDirection getCornerDirection(Side)':
aliens.cpp:175:1: warning: control reaches end of non-void function [-Wreturn-type]
  175 | }
      | ^
aliens.cpp: In function 'Corner getRegionalCorner(Point)':
aliens.cpp:275:1: warning: control reaches end of non-void function [-Wreturn-type]
  275 | }
      | ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10