Submission #173789

#TimeUsernameProblemLanguageResultExecution timeMemory
173789davitmargNice sequence (IZhO18_sequence)C++17
29 / 100
2072 ms262144 KiB
/*DavitMarg*/ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <fstream> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() using namespace std; const int N = 200005 * 5; int gcd(int a, int b) { if (!a || !b) return a + b; return gcd(b, a % b); } int lca(LL a, LL b) { return a * b / gcd(a, b); } int q, n, m, k; vector<int> t, a, used, tin; vector<vector<int>> g; void dfs(int v) { used[v] = 1; for (int i = 0; i < g[v].size(); i++) { int to = g[v][i]; if (used[to]) continue; dfs(to); } tin[v] = -t.size(); t.PB(v); } bool check(int x) { t.clear(); a.resize(x + 2); used.resize(x + 2); tin.resize(x + 2); g.resize(x + 2); for (int i = 0; i <= x; i++) { g[i].clear(); used[i] = 0; a[i] = i; } for (int i = 0; i <= x; i++) { if (i - m >= 0) g[i - m].PB(i); if (i + n <= x) g[i + n].PB(i); } for (int i = 0; i <= x; i++) if (!used[i]) dfs(i); reverse(all(t)); //cout << "!!!!!" << x << endl; for (int i = 0; i < t.size(); i++) { int v = t[i]; for (int j = 0; j < g[v].size(); j++) { int to = g[v][j]; if (tin[to] <= tin[v]) return 0; //cout << v << " : " << to << endl; a[to] = max(a[to], a[v] + 1); } } return 1; } int main() { cin >> q; while (q--) { k = 0; cin >> n >> m; int l, r, mid; l = 0; r = lca(n, m) - 1; while (l <= r) { mid = (l + r) / 2; if (check(mid)) { k = mid; l = mid + 1; } else r = mid - 1; } check(k); cout << k << endl; for (int i = 1; i <= k; i++) printf("%d ", a[i] - a[i - 1]); cout << endl; } return 0; } /* 4 3 1 2 3 1 1 2 2 */

Compilation message (stderr)

sequence.cpp: In function 'void dfs(int)':
sequence.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++)
                     ~~^~~~~~~~~~~~~
sequence.cpp: In function 'bool check(int)':
sequence.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < t.size(); i++)
                     ~~^~~~~~~~~~
sequence.cpp:87:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[v].size(); j++)
                         ~~^~~~~~~~~~~~~
#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...