Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define pb push_back
- #define ll long long
- #define ld long double
- #define pii pair <int,int>
- #define endl '\n'
- #define FILE "nenokku_easy"
- #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
- using namespace std;
- const int mod = 1e9 + 7;
- const int N = 100000;
- const ll inf = 1e18;
- int rd() {
- return (rand() << 15 | rand());
- }
- int in[N + 5];
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- srand(time(0));
- #ifdef LOCAL
- // freopen("input.txt", "r", stdin);
- freopen("input.txt", "w", stdout);
- #else
- //freopen(FILE".in", "r", stdin);
- // freopen(FILE".out", "w", stdout);
- #endif
- int t = 1;
- while (t--) {
- int n = N;
- n = max(n, 2);
- cout << n << endl;
- int root = rd() % n + 1;
- int cnt = rd() % n + 1;
- cnt = min(cnt, n - 1);
- vector <int> used;
- vector <int> perm;
- for (int i = 1; i <= n; i++) {
- if (i == root) continue;
- perm.pb(i);
- }
- int all = n - 1;
- random_shuffle(perm.begin(), perm.end());
- cnt = min(cnt,(int)perm.size());
- int it = 1;
- int e = n - 1 - cnt;
- int st = 0;
- for (int i = 0; i < cnt; i++) {
- if (all == 0) break;
- cout << root << " " << perm[st] << endl;
- in[root]++;
- in[perm[st]]++;
- it++;
- used.pb(perm[st]);
- st++;
- all--;
- }
- random_shuffle(used.begin(), used.end());
- unordered_set <int> good;
- for (auto x : used) good.insert(x);
- int id = 1, sq = (int)sqrt(N);
- for (int i = 0; ; i++) {
- if (all == 0) break;
- int cur = root;
- if (good.size()) {
- cur = *good.begin();
- good.erase(good.begin());
- }
- in[cur]++;
- in[perm[i + st]]++;
- cout << cur << " " << perm[i + st] << endl;
- // cerr << cur << " " << perm[i + st] << endl;
- good.insert(perm[i + st]);
- if (id % 100 == 0) {
- vector <int> kek;
- for (auto x : good) kek.pb(x);
- good.clear();
- random_shuffle(kek.begin(), kek.end());
- for (auto x : kek) good.insert(x);
- }
- id++;
- it++;
- all--;
- }
- //int q = rd() % (3 * N) + 1;
- int q = 3 * N;
- cout << q << endl;
- int x = rd() % n + 1;
- cout << 3 << " " << x << " ";
- x = rd() % n + 1;
- cout << x << endl;
- q--;
- while (q--) {
- int type = rand() % 50 + 1;
- cout << min(type, 3) << " ";
- if (type == 1) {
- int x = rd() % (n - 1) + 1;
- cout << x << endl;
- continue;
- }
- if (type == 2) {
- int x = rd() % (n - 1) + 1;
- cout << x << endl;
- continue;
- }
- {
- int x = rd() % n + 1;
- cout << x << " ";
- int y = rd() % n + 1;
- if (x == y && rd() % 10 != 3){
- while (x == y) y = rd() % n + 1;
- }
- cout << y << endl;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement