Submission #389775

#TimeUsernameProblemLanguageResultExecution timeMemory
389775BartolMNice sequence (IZhO18_sequence)C++17
100 / 100
1557 ms54748 KiB
#define DEBUG 1 #include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back typedef long long ll; typedef pair <int, int> pii; typedef pair <int, pii> pip; typedef pair <pii, int> ppi; typedef pair <ll, ll> pll; const int INF=0x3f3f3f3f; const int N=4e5+5; int n, m; vector <int> ls[N]; //(i->j) i veci od j int in[N], bio[N], sol[N]; queue <int> Q; void reset(int x) { for (int i=0; i<=x; ++i) ls[i].clear(), in[i]=0, bio[i]=0; } void build(int x) { for (int i=1; i<=x; ++i) { if (i-n>=0) ls[i-n].pb(i), in[i]++; if (i-m>=0) ls[i].pb(i-m), in[i-m]++; } } int dfs(int node) { if (bio[node]==2) return 0; if (bio[node]==1) return 1; bio[node]=1; int ret=0; for (int sus:ls[node]) ret|=dfs(sus); bio[node]=2; return ret; } void topo_sort(int gr) { for (int i=0; i<=gr; ++i) if (!in[i]) Q.push(i); int curr=gr+1; while (!Q.empty()) { int node=Q.front(); Q.pop(); sol[node]=curr--; for (int sus:ls[node]) { in[sus]--; if (!in[sus]) Q.push(sus); } } } void solve() { // int lo=0, hi=2*max(n, m), mid; // while (lo<hi) { // mid=(lo+hi+1)/2; // build(mid); // int fl=0; // for (int i=0; i<=mid && !fl; ++i) fl+=dfs(i); // if (fl) hi=mid-1; // else lo=mid; // reset(mid); // } int lo=n+m-__gcd(n, m)-1; build(lo); topo_sort(lo); printf("%d\n", lo); for (int i=1; i<=lo; ++i) printf("%d ", sol[i]-sol[i-1]); printf("\n"); reset(lo); } void load() { scanf("%d %d", &n, &m); } int main() { int t; scanf("%d", &t); while (t--) { load(); solve(); } return 0; }

Compilation message (stderr)

sequence.cpp: In function 'void load()':
sequence.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~
#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...