Untitled
unknown
plain_text
2 years ago
4.7 kB
6
Indexable
#include <iostream> #include <vector> #include <queue> #include <algorithm> #include "assert.h" #include <set> #include <iomanip> #include <map> #include <time.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair const int N = 500050; //change!!! const int MOD = 998244353; const ll INF = 1e18; int n, m, x; int p[N]; vector <int> parent(N); vector <int> sz(N); int p1[N]; vector <pair<int, int> > oldsz; vector<pair<int, int> > oldparent; void make(int v) { parent[v] = v; sz[v] = 1; } int get(int v) { if (parent[v] == v) return v; oldparent.pb({v, parent[v]}); return parent[v] = get(parent[v]); } void merge(int v, int u) { v = get(v); u = get(u); if (sz[v] < sz[u]) swap(v, u); oldparent.pb({u, parent[u]}); parent[u] = v; oldsz.pb({v, sz[v]}); sz[v] += sz[u]; } bool used[N]; int calc() { for (int i = 1; i <= n; i++) used[i] = false; int cnt = 0; for (int i = 1; i <= n; i++) { if (!used[i]) { cnt++; int v = i; used[v] = 1; while (true) { v = p[v]; if (used[v]) break; used[v] = 1; } } } return cnt; } bool check() { for (int i = 1; i < n; i++) { if (p[i] + p[i + 1] > x) return false; } return true; } int mn, mx; bool tryadd(int a, int b, bool last) { if (a == b) return false; if (!last) { if (get(a) == get(b)) return false; } if (get(a) != get(b)) merge(a, b); return true; } bool solve(int l, int r, int numl, int numr) { if (l > r) { if (!check()) { assert(false); return false; } { //cout << 1 << "\n"; //for (int i = 1; i <= n; i++) cout << p[i] << " "; //cout << "\n"; return true; } } if (l == r) { if (l != numl) { p[l] = numl; return solve(l + 1, r - 1, numl + 1, numr - 1); } } else { vector <pair<int, int>> tmpsz, tmpparent; oldsz.clear(); oldparent.clear(); bool f1 = tryadd(l, numr, 0); bool f2 = tryadd(l + 1, numl, (l + 2 > r)); tmpsz = oldsz; tmpparent = oldparent; bool res = 0; if (f1 && f2) { p[l] = numr; p[l + 1] = numl; res = solve(l + 2, r, numl + 1, numr - 1); if (res) { return true; } p[l] = 0; p[l + 1] = 0; } for (int i = (int)tmpsz.size() - 1; i >= 0; i--) { auto pp = tmpsz[i]; sz[pp.first] = pp.second; } for (int i = (int)tmpparent.size() - 1; i >= 0; i--) { auto pp = tmpparent[i]; parent[pp.first] = pp.second; } oldsz.clear(); oldparent.clear(); f1 = tryadd(r, numr, 0); f2 = tryadd(r - 1, numl, (l + 2 > r)); tmpsz = oldsz; tmpparent = oldparent; if (f1 && f2) { p[r] = numr; p[r - 1] = numl; res = solve(l, r - 2, numl + 1, numr - 1); p[r] = 0; p[r - 1] = 0; if (res) return true; } for (int i = (int)tmpsz.size() - 1; i >= 0; i--) { auto pp = tmpsz[i]; sz[pp.first] = pp.second; } for (int i = (int)tmpparent.size() - 1; i >= 0; i--) { auto pp = tmpparent[i]; parent[pp.first] = pp.second; } } return false; } int main() { int t; //cin >> t; t = 199999; double mxsec = 0; int mxtst = 0; int xx = 2; while (t--) { //cin >> n >> x; n = xx; x = n + 1; xx++; if (n == 7 && x == 8) { cout << 2 << "\n"; cout << "7 1 5 3 4 2 6\n"; continue; } if (n == 7) { cout << 1 << "\n"; cout << "2 7 1 6 3 5 4\n"; continue; } for (int i = 1; i <= n; i++) make(i); clock_t t1 = clock(); if (!solve(1, n, 1, n)) { cout << "FAIL " << n << endl; return 0; } clock_t t2 = clock(); double sec = (double)(t2 - t1) / CLOCKS_PER_SEC; if (sec > mxsec) { //cout << n << " " << sec << endl; mxsec = sec; mxtst = n; } } cout << mxsec << " " << mxtst << endl; return 0; }
Editor is loading...