Submission #338122

#TimeUsernameProblemLanguageResultExecution timeMemory
338122BeanZNice sequence (IZhO18_sequence)C++14
100 / 100
1964 ms45668 KiB
// I_Love_LPL #include <bits/stdc++.h> using namespace std; #define ll int #define endl '\n' const int N = 1e6 + 50; long long mod = 1e9 + 7; const int lim = 700; const int lg = 18; const int base = 311; const long double eps = 1e-6; ll n, m; vector<ll> topo; bool vis[N]; ll id[N]; void dfs(ll u, ll mid){ vis[u] = 1; if (u >= m && vis[u - m] == 0) dfs(u - m, mid); if ((u + n) <= mid && vis[u + n] == 0) dfs(u + n, mid); topo.push_back(u); } bool chk(ll mid){ for (int i = 0; i <= mid; i++) vis[i] = 0; topo.clear(); for (int i = 0; i <= mid; i++){ if (vis[i]) continue; dfs(i, mid); } for (int i = 0; i < topo.size(); i++){ id[topo[i]] = i; } for (int u = 0; u <= mid; u++){ if (u >= m && id[u] < id[u - m]) return false; if ((u + n) <= mid && id[u] < id[u + n]) return false; } return true; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("tests.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll t; cin >> t; while (t--){ cin >> n >> m; ll l = 1, h = 4e5 + 1; while (l <= h){ ll mid = (l + h) >> 1; if (chk(mid)) l = mid + 1; else h = mid - 1; } cout << h << endl; chk(h); for (int i = 1; i <= h; i++){ cout << id[i] - id[i - 1] << " "; } cout << endl; } } /* Ans: Out: */

Compilation message (stderr)

sequence.cpp: In function 'bool chk(int)':
sequence.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < topo.size(); i++){
      |                     ~~^~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   43 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...