每日一题5.23

495684945

CCPC郑州 区域赛

C题从第4名银到铜

C题链接

Fengyj

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int long long
typedef pair<int, int> PII;

bool is_pow2(int x) { return x > 0 && (x & (x - 1)) == 0; }

void solve()
{
    int A, B, x, y;
    cin >> A >> B >> x >> y;

    int nn = A, mm = B;
    while (nn % 2 == 0 && nn)
        nn /= 2;
    while (mm % 2 == 0 && mm)
        mm /= 2;
    if ((x && (x % nn)) || (y && (y % mm)))
    {
        cout << -1 << '\n';
        return;
    }

    map<PII, int> mp;
    vector<PII> pos = {{0, 0}, {A, 0}, {0, B}, {A, B}};
    mp[{x, y}] = 1;
    vector<array<int, 4>> ans;
    while (!((x == 0 || x == A) && (y == 0 || y == B)))
    {
        for (auto [nx, ny] : pos)
        {
            int xx = 2 * x - nx;
            int yy = 2 * y - ny;
            if (xx < 0 || xx > A || yy < 0 || yy > B || mp.count({xx, yy}))
                continue;
            mp[{xx, yy}] = 1;
            ans.push_back({nx, ny, xx, yy});
            x = xx;
            y = yy;
            break;
        }
    }
    cout << ans.size() << endl;
    reverse(ans.begin(), ans.end());
    for (auto [a, b, c, d] : ans)
    {
        cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

XinyuLin

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
#include<array>
using namespace std;
using ll = long long;
ll A, B, x, y;
using info = array<ll, 4>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> A >> B;
	cin >> x >> y;
	bool ok1 = false, ok2 = false;
	ll fi = 0, fj = 0;
	ll l = 0, r = A, mid;
	vector<info> ans;
	
	if (x == A || x == 0) {
		ok1 = true;
	}
	if (y == B || y == 0) {
		ok2 = true;
	}
	if (!ok1) {
		while ((l + r) % 2 == 0) {
			fi++;
			mid = (l + r) / 2;
			if (x == mid) {
				ok1 = true;
				break;
			}
			else if (x > mid) {
				l = mid;
			}
			else {
				r = mid;
			}
		}
	}
	l = 0, r = B;
	if (!ok2) {
		while ((l + r) % 2 == 0) {
			fj++;
			mid = (l + r) / 2;
			if (y == mid) {
				ok2 = true;
				break;
			}
			else if (y > mid) {
				l = mid;
			}
			else {
				r = mid;
			}
		}
	}
	// 判断存在
	if (!ok1 || !ok2) {
		cout << -1 << endl;
		return 0;
	}
	// 反推
	ll tx = x, ty = y;
	for (int i = 1; i <= max(fi, fj); i++) {
		ll t1, t2, t3, t4;
		if (tx >= A / 2) {
			t1 = 2 * tx - A;
			t3 = A;
		}
		else {
			t1 = 2 * tx;
			t3 = 0;
		}
		if (ty >= B / 2) {
			t2 = 2 * ty - B;
			t4 = B;
		}
		else {
			t2 = 2 * ty;
			t4 = 0;
		}
		tx = t1;
		ty = t2;
		ans.push_back({ t1, t2, t3, t4 });
	}
	reverse(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++) {
		for (int j = 0; j < 4; j++) {
			cout << ans[i][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}

495684945

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
using i128 = __int128_t;

struct Node { int x1, y1, x2, y2; };

bool is_pow2(int x) { return x && !(x & (x - 1)); }

void solve() {
	int a, b, x, y;
	if (!(cin >> a >> b >> x >> y)) return;
	
	if ((a == 0 && x != 0) || (b == 0 && y != 0)) {
		cout << -1 << '\n';
		return;
	}

	int k = 0;
	bool ok = true;
	auto upd = [&](int A, int X) {
		if (A == 0) return;
		int g = std::gcd(A, X);
		int need = A / g;                
		if (!is_pow2(need)) { ok = false; return; }
		k = max<int>(k, __builtin_ctzll(need));
	};
	upd(a, x);
	upd(b, y);
	if (!ok) { cout << -1 << '\n'; return; }
	

	i128 ix = a ? ((i128)x << k) / a : 0;
	i128 iy = b ? ((i128)y << k) / b : 0;
	int lim = 1LL << k;
	if (ix < 0 || ix > lim || iy < 0 || iy > lim) {       
		cout << -1 << '\n';
		return;
	}
	

	bool lock_x = (a && (x == 0 || x == a));
	bool lock_y = (b && (y == 0 || y == b));
	

	vector<Node> ans;
	int tx = x, ty = y;
	for (int i = k - 1; i >= 0; --i) {
		int qx, qy, px, py;
		

		if (lock_x || a == 0) {
			qx = (a == 0 ? 0 : (x == a ? a : 0));
			px = tx;               
		} else {
			int bx = (ix >> i) & 1;
			qx = bx ? a : 0;
			px = 2 * tx - qx;
		}
		
		if (lock_y || b == 0) {
			qy = (b == 0 ? 0 : (y == b ? b : 0));
			py = ty;
		} else {
			int by = (iy >> i) & 1;
			qy = by ? b : 0;
			py = 2 * ty - qy;
		}
		
		ans.push_back({qx, qy, px, py});  
		tx = px; ty = py;                 
	}
	reverse(ans.begin(), ans.end());
	
	cout << ans.size() << '\n';
	for (auto [x1, y1, x2, y2] : ans)
		cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}