Submission #6390145


Source Code Expand

Copy
    #define _USE_MATH_DEFINES
    #include "bits/stdc++.h"
    using namespace std;
     
    //template
    #define rep(i,a,b) for(int i=(a);i<(b);i++)
    #define rrep(i,a,b) for(int i=(a);i>(b);i--)
    typedef long long int ll; typedef pair<ll, ll> P; typedef complex<double> com;
    template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
    template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
    ll gcd(ll a, ll b) { if (!b)return a; else return gcd(b, a % b); }
    const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
    int mod = 1e9 + 7; //998244353;
    struct Mint {
    	int val;
    	Mint inv() const {
    		unsigned tmp, a = val, b = mod; int x = 1, y = 0;
    		while (b) tmp = a / b, a -= tmp * b, swap(a, b), x -= tmp * y, swap(x, y);
    		return Mint(x);
    	}
    public:
    	Mint() :val(0) {}
    	Mint(ll x) :val(x >= 0 ? x % mod : x % mod + mod) {}
    	int mtoi() { return this->val; }
    	Mint pow(ll t) { Mint res = 1; while (t > 0) { if (t & 1) res *= *this; *this *= *this; t >>= 1; }return res; }
    	Mint& operator+=(const Mint& x) { if ((val += x.val) >= mod) val -= mod; return *this; }
    	Mint& operator-=(const Mint& x) { if ((val += mod - x.val) >= mod) val -= mod; return *this; }
    	Mint& operator*=(const Mint& x) { val = (ll)val * x.val % mod; return *this; }
    	Mint& operator/=(const Mint& x) { return *this *= x.inv(); }
    	bool operator==(const Mint& x) const { return val == x.val; }
    	bool operator!=(const Mint& x) const { return val != x.val; }
    	bool operator<(const Mint& x) const { return val < x.val; }
    	bool operator<=(const Mint& x) const { return val <= x.val; }
    	bool operator>(const Mint& x) const { return val > x.val; }
    	bool operator>=(const Mint& x) const { return val >= x.val; }
    	Mint operator-() const { return Mint(-val); }
    	Mint operator+(const Mint& x) const { return Mint(*this) += x; }
    	Mint operator-(const Mint& x) const { return Mint(*this) -= x; }
    	Mint operator*(const Mint& x) const { return Mint(*this) *= x; }
    	Mint operator/(const Mint& x) const { return Mint(*this) /= x; }
    };
    struct factorial {
    	vector<Mint> Fact, Finv;
    public:
    	factorial(int maxx) {
    		Fact.resize(maxx + 1, Mint(1)); Finv.resize(maxx + 1);
    		rep(i, 0, maxx) Fact[i + 1] = Fact[i] * Mint(i + 1);
    		Finv[maxx] = Mint(1) / Fact[maxx];
    		rrep(i, maxx, 0) Finv[i - 1] = Finv[i] * Mint(i);
    	}
    	Mint fact(int n) { return Fact[n]; }
    	Mint finv(int n) { return Finv[n]; }
    	Mint nCr(int n, int r) {
    		if (n < 0 || n < r || r < 0) return Mint(0);
    		return Fact[n] * Finv[r] * Finv[n - r];
    	}
    	Mint nPr(int n, int r) {
    		if (n < 0 || n < r || r < 0) return Mint(0);
    		return Fact[n] * Finv[n - r];
    	}
    };
    class UnionFind {
    	vector<int> par;
    public:
    	UnionFind(int n) { par = vector<int>(n, -1); }
    	int root(int a) {
    		if (par[a] < 0) return a;
    		else return par[a] = root(par[a]);
    	}
    	int size(int a) { return -par[root(a)]; }
    	bool connect(int a, int b) {
    		a = root(a), b = root(b);
    		if (a == b) return false;
    		if (size(a) < size(b)) swap(a, b);
    		par[a] += par[b], par[b] = a;
    		return true;
    	}
    };
    struct max_flow {
    	struct Edge { int to, cap, rev; };
    	int V; vector<vector<Edge>> G; vector<int> itr, level;
    public:
    	max_flow(int V) : V(V) { G.assign(V, vector<Edge>()); }
    	void add_edge(int from, int to, int cap) {
    		G[from].push_back({ to, cap, (int)G[to].size() });
    		G[to].push_back({ from, 0, (int)G[from].size() - 1 });
    	}
    	void bfs(int s) {
    		level.assign(V, -1); queue<int> q;
    		level[s] = 0; q.push(s);
    		while (!q.empty()) {
    			int v = q.front(); q.pop();
    			for (auto& e : G[v]) {
    				if (e.cap > 0 && level[e.to] < 0) {
    					level[e.to] = level[v] + 1;
    					q.push(e.to);
    				}
    			}
    		}
    	}
    	int dfs(int v, int t, int f) {
    		if (v == t) return f;
    		for (int& i = itr[v]; i < (int)G[v].size(); ++i) {
    			Edge& e = G[v][i];
    			if (e.cap > 0 && level[v] < level[e.to]) {
    				int d = dfs(e.to, t, min(f, e.cap));
    				if (d > 0) {
    					e.cap -= d, G[e.to][e.rev].cap += d;
    					return d;
    				}
    			}
    		}
    		return 0;
    	}
    	int run(int s, int t) {
    		int ret = 0, f;
    		while (bfs(s), level[t] >= 0) {
    			itr.assign(V, 0);
    			while ((f = dfs(s, t, inf)) > 0) ret += f;
    		}
    		return ret;
    	}
    };
    struct edge { int u, v, cost; };
    vector<ll> dijkstra(vector<vector<edge>> Grp, int s) {
    	priority_queue<P, vector<P>, greater<P> > que;
    	vector<ll> dist(Grp.size(), INF); dist[s] = 0; que.push(P(0, s));
    	while (!que.empty()) {
    		P p = que.top(); que.pop();
    		int v = p.second; if (dist[v] < p.first) continue;
    		rep(i, 0, Grp[v].size()) {
    			edge e = Grp[v][i];
    			if (dist[e.v] > dist[v] + e.cost) {
    				dist[e.v] = dist[v] + e.cost;
    				que.push(P(dist[e.v], e.v));
    			}
    		}
    	} return dist;
    }
    void fft(vector<com>& x, bool inv) {
    	int s = x.size(); if (s == 1) return;
    	vector<com> even(s / 2), odd(s / 2);
    	rep(i, 0, s / 2)even[i] = x[i * 2], odd[i] = x[i * 2 + 1];
    	fft(even, inv), fft(odd, inv);
    	com w = 1, w_0 = polar(1.0, (inv ? -1 : 1) * 2LL * M_PI / s);
    	rep(i, 0, s)x[i] = even[i % (s / 2)] + w * odd[i % (s / 2)], w *= w_0;
    }
    void MultiFunction(vector<int>& a, vector<int>& b) {
    	int n = a.size(), maxx = 1; while (maxx <= 2 * n)maxx *= 2;
    	vector<com> x(maxx), y(maxx);
    	rep(i, 0, n) x[i] = com(a[i], 0), y[i] = com(b[i], 0);
    	fft(x, 0), fft(y, 0); rep(i, 0, maxx) x[i] *= y[i];
    	fft(x, 1); rep(i, 0, maxx)x[i] /= maxx;
    	a.resize(2 * n - 1, 0);
    	rep(i, 0, 2 * n - 1)a[i] = (int)(x[i].real() + 0.5);
    }
    ll merge_cnt(vector<int> a) {
    	ll n = a.size(), ai = 0, bi = 0, ci = 0, cnt = 0;
    	if (n <= 1) return 0;
    	vector<int> b(a.begin(), a.begin() + n / 2);
    	vector<int> c(a.begin() + n / 2, a.end());
    	cnt += merge_cnt(b) + merge_cnt(c);
    	while (ai < n) {
    		if (bi < b.size() && (ci == c.size() || b[bi] <= c[ci]))a[ai++] = b[bi++];
    		else cnt += n / 2LL - bi, a[ai++] = c[ci++];
    	}
    	return cnt;
    }
    //template end
     
     
     
    int main() {
    	int n; cin >> n;
    	int t = log2(n);
    	if (n == pow(2, t)) {
    		printf("No"); return 0;
    	}
    	printf("Yes\n");
    	vector<P> ans;
    	ans.push_back({ n + 1,n + 2 });
    	rep(i, 2, n) {
    		ans.push_back({ 1,i });
    		ans.push_back({ 1,i + 1 });
    		ans.push_back({ i + 1,i + n });
    		ans.push_back({ i,i + n + 1 });
    		i++;
    	}
    	if (n % 2 == 0) {
    		int a, b;
    		rep(i, 2, n) {
    			a = i; b = i ^ (n+1);
    			if (b >= 2 && b < n && a != b)break;
    		}
    		ans.push_back({ n,a });
    		ans.push_back({ b,2 * n });
    	}
    	rep(i, 0, ans.size())printf("%lld %lld\n", ans[i].first, ans[i].second);
    	return 0;
    }

Submission Info

Submission Time
Task C - Skolem XOR Tree
User priyam2k
Language C++14 (GCC 5.4.1)
Score 700
Code Size 7318 Byte
Status AC
Exec Time 33 ms
Memory 6508 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 2
AC × 37
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, sample_01.txt, sample_02.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt
Case Name Status Exec Time Memory
hand_01.txt AC 1 ms 256 KB
hand_02.txt AC 1 ms 256 KB
hand_03.txt AC 1 ms 256 KB
hand_04.txt AC 1 ms 256 KB
hand_05.txt AC 1 ms 256 KB
hand_06.txt AC 1 ms 256 KB
hand_07.txt AC 1 ms 256 KB
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
test_01.txt AC 1 ms 256 KB
test_02.txt AC 1 ms 256 KB
test_03.txt AC 1 ms 256 KB
test_04.txt AC 1 ms 256 KB
test_05.txt AC 1 ms 256 KB
test_06.txt AC 1 ms 256 KB
test_07.txt AC 1 ms 256 KB
test_08.txt AC 1 ms 256 KB
test_09.txt AC 1 ms 256 KB
test_10.txt AC 1 ms 256 KB
test_11.txt AC 1 ms 256 KB
test_12.txt AC 1 ms 256 KB
test_13.txt AC 1 ms 256 KB
test_14.txt AC 1 ms 256 KB
test_15.txt AC 1 ms 256 KB
test_16.txt AC 1 ms 256 KB
test_17.txt AC 33 ms 6508 KB
test_18.txt AC 33 ms 5484 KB
test_19.txt AC 33 ms 6000 KB
test_20.txt AC 33 ms 5616 KB
test_21.txt AC 9 ms 1524 KB
test_22.txt AC 3 ms 640 KB
test_23.txt AC 8 ms 1524 KB
test_24.txt AC 14 ms 2420 KB
test_25.txt AC 9 ms 1524 KB
test_26.txt AC 14 ms 2420 KB
test_27.txt AC 9 ms 1524 KB
test_28.txt AC 25 ms 6256 KB