Submission #343989

#TimeUsernameProblemLanguageResultExecution timeMemory
343989RakhmandNice sequence (IZhO18_sequence)C++14
100 / 100
1330 ms54372 KiB
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <queue> #include <cmath> #include <cstdlib> #include <ctime> #include <cassert> #include <iterator> using namespace std; #define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0); #define S second #define F first #define pb push_back #define nl '\n' #define NL cout << '\n'; #define EX exit(0) #define all(s) s.begin(), s.end() #define no_answer {cout << "NO"; exit(0);} #define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k) const long long mxn = 4e5 + 110; const long long mnn = 1e3 + 2; const long long mod = 1e9 + 7; const long long inf = 1e18; const long long OO = 1e8; typedef long long llong; typedef unsigned long long ullong; int n, m, k; int pr[mxn], a[mxn]; int used[mxn]; vector<int> top; bool dfs(int x){ used[x] = 1; bool ok = 1; if (x + n <= k) { if (!used[x + n]) ok &= dfs(x + n); else if (used[x + n] == 1) return false; } if (x - m >= 1) { if (!used[x - m]) ok &= dfs(x - m); else if (used[x - m] == 1) return false; } used[x] = 2; return ok; } bool check(int K){ k = K; for(int i = 1; i <= k; i++){ used[i] = 0; } return dfs(1); } void dfss(int x){ used[x] = 1; if (x + n <= k) { if (used[x + n] == 0) dfss(x + n); } if (x - m >= 1) { if (used[x - m] == 0) dfss(x - m); } top.push_back(x); } void solve(){ cin >> n >> m; if(n == m){ cout << n - 1 << nl; for(int i = 1; i < n; i++){ cout << 1 << ' '; } cout << nl; return ; } if(n == 1 || m % n == 0){ cout << m - 1 << nl; for(int i = 1; i <= m - 1; i++) cout << -1 << ' '; cout << nl; return ; } if(m == 1 || n % m == 0){ cout << n - 1 << nl; for(int i = 1; i <= n - 1; i++) cout << 1 << ' '; cout << nl; return ; } int l = 0, r = n + m + 1; while(r - l > 1){ int mid = (l + r) / 2; if(check(mid)){ l = mid; }else{ r = mid; } } k = -1; if(check(r)) k = r; else k = l; for(int i = 1; i <= k; i++){ used[i] = 0; } top.clear(); cout << k - 1 << nl; for(int i = 1; i <= k; i++){ if(used[i] == 0){ dfss(i); } } reverse(top.begin(), top.end()); for(int i = 0; i < top.size(); i++){ pr[top[i]] = OO - i; } for(int i = 2; i <= k; i++){ pr[i] -= pr[1]; } pr[1] = 0; for(int i = 2; i <= k; i++){ a[i] = pr[i] - pr[i - 1]; } for(int i = 2; i <= k; i++){ cout << a[i] << ' '; } cout << nl; } int main() { ios; int t; cin >> t; while(t--){ solve(); } }

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for(int i = 0; i < top.size(); i++){
      |                    ~~^~~~~~~~~~~~
#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...