Submission #341936

#	Time	Username	Problem	Language	Result	Execution time	Memory
341936		ivan_tudor	Nice sequence (IZhO18_sequence)	C++14	100 / 100	1820 ms	46836 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
const int N= 4*1e5 + 5;
bool viz[N];
int val[N];
int n, m;
vector<int> ord;
void dfs(int nod, int len){
  viz[nod] = true;
  if(nod + n<=len && viz[nod + n] == 0)
    dfs(nod + n, len);
  if(nod - m >=0 && viz[nod - m]==0)
    dfs(nod - m , len);
  ord.push_back(nod);
}
int ans[N];
void clr(int len){
  for(int i=0; i<=len;i++){
    val[i] = 0, viz[i] = 0;
  }
  ord.clear();
}
bool check(int len){
  int cnt = 0;
  for(int i=0;i<=len;i++){
    if(viz[i] == 0)
      dfs(i, len);
  }
  for(int i = 0; i< ord.size();i++){
    val[ord[i]]= i;
  }
  for(int i=1; i<=len;i++){
    if(i-n>=0 && val[i] > val[i - n]){
      clr(len);
      return false;
    }
    if(i - m >=0 && val[i] < val[i - m]){
      clr(len);
      return false;
    }
  }
  for(int i=1;i<=len;i++){
    ans[i] = val[i] - val[i -1];
  }
  clr(len);
  return true;
}
void solve(){
  cin>>n>>m;
  int pas = 0;
  for(int p2 = 1<<20; p2 > 0; p2>>=1){
    if(pas + p2 < N && check(pas + p2))
      pas += p2;
  }
  cout<<pas<<"\n";
  for(int i=1; i<=pas; i++){
    cout<<ans[i]<<" ";
  }
  cout<<"\n";
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int nrt;
  cin>>nrt;
  for(int i=1;i<=nrt;i++){
    solve();
  }
  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'bool check(int)':
sequence.cpp:29:19: 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< ord.size();i++){
      |                  ~^~~~~~~~~~~~
sequence.cpp:24:7: warning: unused variable 'cnt' [-Wunused-variable]
   24 |   int cnt = 0;
      |       ^~~

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24