Submission #173823

#TimeUsernameProblemLanguageResultExecution timeMemory
173823davitmargNice sequence (IZhO18_sequence)C++17
76 / 100
2056 ms100044 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 = 10 * 200005; int gcd(int a, int b) { if (!a || !b) return a + b; return gcd(b, a % b); } LL lca(LL a, LL b) { return a * b / gcd(a, b); } int q, n, m, k, a[N], used[N], tin[N]; vector<int> t, g[N]; 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(); for (int i = 0; i <= x; i++) g[i].clear(); 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); //cout << "!!!!!" << x << endl; int v, to; for (int i = t.size() - 1; i >= 0; i--) { v = t[i]; a[v] = t.size() - i; for (int j = 0; j < g[v].size(); j++) { 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; } char uu[12]; void tp(int x) { if (x == 0) { putchar('0'); return; } if (x < 0) { putchar('-'); x *= (-1); } int i = 0; while (x) { uu[i++] = (x % 10) + '0'; x /= 10; } for (i = i - 1; i >= 0; --i) putchar(uu[i]); } int main() { cin >> q; while (q--) { k = 0; cin >> n >> m; LL l, r, mid; l = 0; r = n + m - 1; // while (l <= r) // { // mid = (l + r) / 2; // if (check(mid)) // { // k = mid; // l = mid + 1; // } // else // r = mid - 1; // } k = n + m - gcd(n, m) - 1; check(k); tp(k); putchar('\n'); for (int i = 1; i <= k; i++) { //printf("%d ", a[i] - a[i - 1]); tp(a[i] - a[i - 1]); putchar(' '); used[i] = 0; } used[0] = 0; putchar('\n'); } return 0; } /* 4 3 1 2 3 1 1 2 2 */

Compilation message (stderr)

sequence.cpp: In function 'void dfs(int)':
sequence.cpp:46: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:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[v].size(); j++)
                         ~~^~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:121:12: warning: variable 'l' set but not used [-Wunused-but-set-variable]
         LL l, r, mid;
            ^
sequence.cpp:121:15: warning: variable 'r' set but not used [-Wunused-but-set-variable]
         LL l, r, mid;
               ^
sequence.cpp:121:18: warning: unused variable 'mid' [-Wunused-variable]
         LL l, r, mid;
                  ^~~
#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...