Submission #1154653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154653		jmuzhen	Aliens (IOI07_aliens)	C++20	0 / 100	1 ms	464 KiB

aliens

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

#define int long long

int N;

// #define cerr if (false) cerr
#define assert(x) ;

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 = DIAGONAL_LEFT;
    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;
    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(Point p, 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 p2 = binarySearchGetPointHelper(fixed_x, fixed_y, m);
        bool R = query(p2);
        // 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 = p;
    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,r1,l2,r2;
    if (di == DIAGONAL_RIGHT) {
        l1 = -min(p.x - 1, p.y - 1), r1 = 0;
        l2 = 0, r2 = min(N - p.x, N - p.y);
    }
    else {
        l1 = -min(p.x-1, N-p.y), r1=0;
        l2=0, r2=min(N - p.x, p.y - 1);
    }

    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);

    cerrP(p1,"dp1");
    cerrP(p2,"dp2");

    if (p1.x > p2.x) swap(p1,p2);

    // take midpoint
    if ((p1.x + p2.x) % 2 == 0)
    return {(p1.x+p2.x)/2, (p1.y+p2.y)/2};
    else {
        if ((p2.x-p1.x) == 0) return p1;
        // must take a point on the actual diagonal, eg. (18,3),(19,2) cannot give (18,2)
        // note that p2.y - p1.y / p2.x - p1.x = mp.y - p1.y / mp.x - p1.x
        //-> (p2.x-p1.x) (mp.y-p1.y) = (p2.y-p1.y)(mp.x-p1.x) which is a constant
        int mpx = (p1.x+p2.x)/2;
        return {mpx, (p2.y-p1.y) * (mpx-p1.x) / (p2.x-p1.x) + p1.y};
    }
}


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
        /// instead, pick a diagonal and get from there
        // p = diagonallyOffset(p, DIAGONAL_LEFT, 1);
        p.x+=1;
        return getRegionalCorner(p);
    }
    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;
        }

        cerr << "binarysearchHelper(" << fixed_x << " " << fixed_y << " " << bsl << " " << bsr << " \n";

        int var = binarySearchHelper(p, fixed_x, fixed_y, bsl, bsr, true);
        cerr << "var=" << var << endl;
        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;
    //     rcenter = binarySearchMidpointDiagonal(rc.p, rc.di);
    // }
    // then get the diagonal midpoint (regional center)
    // else {
        rcenter = binarySearchMidpointDiagonal(rc.p, rc.di);
    // }

    cerrP(rcenter, "rcenter");

    // find the midpoint of current rcenter's other diagonal
    // otherdi = rc.di;
    Diagonal otherdi = (Diagonal)(1 - rc.di);
    Point rcenter_diag_mp = binarySearchMidpointDiagonal(rcenter, otherdi);
    output(rcenter_diag_mp);
    //
    // 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, rc.di);
    // output(gcenter);

    return 0;
}

Compilation message (stderr)

aliens.cpp:9: warning: "assert" redefined
    9 | #define assert(x) ;
      | 
In file included from /usr/include/c++/11/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from aliens.cpp:1:
/usr/include/assert.h:92: note: this is the location of the previous definition
   92 | #  define assert(expr)                                                  \
      | 
aliens.cpp: In function 'Diagonal getDiagonalFromCornerDirection(CornerDirection)':
aliens.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
   84 | }
      | ^
aliens.cpp: In function 'Point binarySearchGetPointHelper(long long int, long long int, long long int)':
aliens.cpp:126:1: warning: control reaches end of non-void function [-Wreturn-type]
  126 | }
      | ^
aliens.cpp: In function 'Side getSide(std::vector<long long int>)':
aliens.cpp:170:1: warning: control reaches end of non-void function [-Wreturn-type]
  170 | }
      | ^
aliens.cpp: In function 'CornerDirection getCornerDirection(Side)':
aliens.cpp:177:1: warning: control reaches end of non-void function [-Wreturn-type]
  177 | }
      | ^
aliens.cpp: In function 'Corner getRegionalCorner(Point)':
aliens.cpp:305:1: warning: control reaches end of non-void function [-Wreturn-type]
  305 | }
      | ^

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