Skip to content

Instantly share code, notes, and snippets.

@tmt514 tmt514/plo.cpp
Created Feb 27, 2016

Embed
What would you like to do?
// by tmt514
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#define SZ(x) ((int)(x).size())
#define FOR(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
using namespace std;
typedef long long LL;
int n, m;
vector<LL> ans;
void ask(LL x, LL y, int limit, int dir, LL step) {
if (x==0 && y==0) {
ans.push_back(step);
return;
}
if (x==1 && y==1) {
ans.push_back(step + dir);
return;
}
LL edx=1, edy=1, xl=0, xr=1, yl=0, yr=1;
for(int i=1;i<=limit;i++) {
LL nedx=-edy+edx, nedy=edx+edy;
LL nyl = nedy-xr;
LL nyr = nedy-xl;
LL nxl = nedx+yl;
LL nxr = nedx+yr;
if (nxl <= x && nxr >= x && nyl <= y && nyr >= y) {
ask(-(y-nedy), x-nedx, i-1, -dir, step + dir*(1LL<<(i)));
}
edx = nedx;
edy = nedy;
yl = min(yl, nyl);
yr = max(yr, nyr);
xl = min(xl, nxl);
xr = max(xr, nxr);
}
}
int main(void) {
scanf("%d%d", &n, &m);
while(m--) {
LL x, y;
scanf("%lld%lld", &x, &y);
ans = vector<LL>();
if (x == 0 && y == 0)
ans.push_back(0);
ask(x, y, min(n, 120), 1, 0);
sort(ans.begin(), ans.end());
ans = vector<LL>(ans.begin(), unique(ans.begin(), ans.end()));
printf("%d", (int)ans.size());
FOR(it, ans) {
LL s = *it;
printf(" %lld", s);
}
puts("");
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.