Submission #581674

#	Time	Username	Problem	Language	Result	Execution time	Memory
581674		HunterXD	Toys (CEOI18_toy)	C++17	100 / 100	2416 ms	86724 KiB

toy

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector <char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef pair<ll,ll> pl;
typedef double dou;
typedef vector<pl> vpl;
typedef unsigned long long ull;
typedef uint64_t i64;
typedef vector<ull> vull;

#define f first 
#define s second 
#define pb push_back 
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define ts to_string
#define lb lower_bound 
#define ub upper_bound
#define yes cout<<'Y'<<'E'<<'S'<<endl
#define no cout<<'N'<<'O'<<endl
#define nd "\n"

void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
 
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll mcm(ll a, ll b) {return (a * b) / gcd(a, b);}
bool prime(ll n) {for(int i=2; i<=sqrt(n); i++) if(n%i==0) return false; return true;}
struct compii{bool operator()(const ii &a, const ii &b){if(a.f==a.s)return a.s<b.s;return a.f>b.f;}};
bool comp(int a, int b) {return a>b;}
ll binpow(ll n, ll x){ll ans=1; while(x){if(x&1){ans*=n;}n*=n; x>>=1;} return ans;}

namespace operators {
template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& x){in >> x.first >> x.second;return in;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2> x){out << x.first << " " << x.second;return out;}
template<typename T1>istream& operator>>(istream& in, vector<T1>& x) {for (auto& i : x) in >> i;return in;}
template<typename T1>ostream& operator<<(ostream& out, vector<T1>& x) {for (auto& i : x) out << i << " ";return out;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, vector<pair <T1,T2>>& x) {for (auto& i : x) out << i.f << " "<<i.s;return out;}
template<typename T1, typename T2>istream& operator>>(istream& in, vector<pair <T1,T2>>& x) {for (auto& i : x) in >> i.f >>i.s;return in;}
}

using namespace operators;

int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};

const int pmod = 998244353;
const int mod = 1e9+7;
const ll inf=1e18;

ll sum(ll a, ll b){
  return (( (a+mod) %mod) + ((b+mod)%mod))%mod;
}

ll multi(ll a, ll b){
  return (((a+mod) %mod) * ((b+mod)%mod))%mod;
}

///

vector<ll> divi;
ll llevo = 1;

vector<pl> divide(ll n){

  vector<pl> res;
  ll counter = 0;
  while(n%2 == 0){
    n/= 2;
    counter++;
  }
  if(counter) res.pb({2, counter});

  for(ll i = 3; i*i <= n; i+= 2){
    counter = 0;
    while(n%i == 0){
      n/= i;
      counter++;
    }
    if(counter) res.pb({i, counter});
  }

  if(n != 1) res.pb({n, 1});
  return res;
}

void calc_div(vector<pl> &me, ll pos){
  if(pos == me.size()){
    divi.pb(llevo);
    return;
  }

  ll c = me[pos].s;
  ll temp = 1;
  for(ll i = 0; i <= c; i++){
    llevo*= temp;
    calc_div(me, pos+1);
    llevo/= temp;
    temp*= me[pos].f;
  }
}

void solve(){

  ll n;
  cin >> n;

  vector<pl> me = divide(n);
  llevo = 1;
  calc_div(me, 0);

  sort(all(divi));
  
  ll m = divi.size(), temp;
  vector< set<ll> > res(m, set<ll>());
  
  for(ll i = 0; i < m; i++){
    for(ll i2 = 0; i2 < i; i2++){
      if(divi[i]%divi[i2]) continue;
      temp = divi[i]/divi[i2];
      for(auto v: res[i2]){
        res[i].insert(v + temp-1);   
      }
    }
    res[i].insert(divi[i]-1);
  }

  cout << res[m-1].size() << endl;
  for(auto v: res[m-1]){
    cout << v << " ";
  }
  cout << endl;
}

int main (){
  setIO("");
  int t = 1;
  //cin >> t;
  while(t-->0) solve();
  return 0;
}

Compilation message (stderr)

toy.cpp: In function 'void calc_div(std::vector<std::pair<long long int, long long int> >&, ll)':
toy.cpp:98:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   if(pos == me.size()){
      |      ~~~~^~~~~~~~~~~~
toy.cpp: In function 'void setIO(std::string)':
toy.cpp:34:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toy.cpp:34:128: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
      |                                                                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 21 / 21