Submission #166810

#TimeUsernameProblemLanguageResultExecution timeMemory
166810YaroslaffNice sequence (IZhO18_sequence)C++14
100 / 100
1902 ms47796 KiB
#pragma GCC target ("avx2,sse2") #pragma GCC optimization ("Ofast") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> #define ll long long #define db long double #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define fi first #define se second #define mp make_pair #define up_b upper_bound #define low_b lower_bound #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() //#define endl "\n" #define left fsdkfsdfsdfd #define sum dfsdfsdfsdf #define assign sdkfskdfkk //#define int long long using namespace std; void dout() { cerr << endl; } template <typename Head, typename... Tail> void dout(Head H, Tail... T) { cerr << H << ' '; dout(T...); } //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef pair <int, int> pii; int bit(signed x) { return __builtin_popcount(x); } int bit(ll x) { return __builtin_popcountll(x); } const int N = 4e5 + 123; int n, m, k, used[N], p[N], a[N]; bool cycle; vector <int> topsort; void cleanup() { cycle = false; topsort = {}; for (int i = 0; i <= k; i++) { used[i] = p[i] = a[i] = 0; } k = 0; } void dfs(int v) { used[v] = 1; if (v - n >= 0) { if (used[v - n] == 1) { cycle = true; return; } if (used[v - n] == 0) { dfs(v - n); } } if (v + m <= k) { if (used[v + m] == 1) { cycle = true; return; } if (used[v + m] == 0) { dfs(v + m); } } used[v] = 2; } void get(int v) { used[v] = 1; if (v - n >= 0) { if (!used[v - n]) { get(v - n); } } if (v + m <= k) { if (!used[v + m]) { get(v + m); } } topsort.pb(v); } bool check() { if (k == 0) { return true; } cycle = false; for (int i = 0; i <= k; i++) { if (used[i] == 0) { dfs(i); } } for (int i = 0; i <= k; i++) { used[i] = 0; } return !cycle; } void construct() { for (int i = 0; i <= k; i++) { if (used[i] == 0) { get(i); } } reverse(topsort.begin(), topsort.end()); for (int i = 0; i <= k; i++) { p[topsort[i]] = i; } bool zero = false; for (int i = 1; i <= k; i++) { a[i] = p[i] - p[i - 1]; if (a[i] == 0) { zero = true; } } cout << k << endl; for (int i = 1; i <= k; i++) { if (zero) { a[i]++; } cout << a[i] << " "; } cout << endl; } void solve(int tc) { // check for (int i = 0; i < n; j++) cin >> n >> m; int l = min(n, m) - 2, r = n + m + 7; while (l < r - 1) { int mid = l + r >> 1; k = mid; if (check()) { l = mid; } else { r = mid; } } k = l; construct(); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tc = 1; cin >> tc; for (int i = 0; i < tc; i++) { solve(i); cleanup(); } }

Compilation message (stderr)

sequence.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")
 
sequence.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
sequence.cpp: In function 'void solve(int)':
sequence.cpp:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...