| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 168824 |
2019-12-16T15:34:32 Z |
kostia244 |
Toys (CEOI18_toy) |
C++17 |
|
230 ms |
262148 KB |
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,sse2,sse,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC comment("/STACK:26666666")
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using vi = vector<int>;
const int mod = 1e9 + 7;
int n;
int cnt = 0, dcnt = 0, anscnt = 0;
bitset<1200200> *vis;//exact upper bound +1
bitset<6969569> *vis2;//exact upper bound +1
bitset<1000001> goods, goodb;
int ans[80808], go[10203];
int *a, *b, sz = 0;
int x, z, zz;
ll u;
__attribute__((always_inline)) void sset(int i) {
if(i < 1000001)
goods.set(i);
else
goodb.set(n/i);
}
__attribute__((always_inline)) bool gget(int i) {
if(i < 1000001)
return goods.test(i);
else
return goodb.test(n/i);
}
__attribute__((always_inline)) inline bool mark(int i, int cur) {
x = 0;
for(int z = 1<<10; z; z>>=1)
if(x+z<dcnt&&go[x+z]<=i) x+=z;
z = (3ll*cur + 1)%1002523;
zz = (65ll*cur + 2)%6969569;
if(vis[x][z]&&vis2[x][zz]) return false;
vis[x][z] = 1;
vis2[x][zz] = 1;
return true;
}
__attribute__((always_inline)) inline void dfs(int i, int cur) {
if(i>n) return;
cnt++;
if(i == n) {
ans[anscnt++] = cur;
return;
}
for(int k = 0; k < dcnt; k++) {
u = i*1ll*go[k];
if(u>n) break;
if(gget(u)&&mark(u, cur+go[k]-1)){
a[sz] = u;
b[sz] = cur+go[k]-1;
sz++;
}
}
}
__attribute__((always_inline)) void solve() {
a[0] = 1;
b[0] = 0;
mark(1, 0);
sz = 1;
int i = 0;
while(i < sz) {
dfs(a[i], b[i]);
i++;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
a = new int[50000001];
b = new int[50000001];
vis = new bitset<1200200>[1345];
vis2 = new bitset<6969569>[1345];
cin >> n;
ll tn = n;
for(ll i = 1; i*i <= tn; i++) {
if(tn%i) continue;
if(i>1) {
go[dcnt++] = i;
sset(i);
}
if(i*i!=n)
go[dcnt++] = n/i, sset(n/i);
}
sort(go, go+dcnt);
solve();
// cerr<< cnt << "\n";
sort(ans, ans+anscnt);
cout << anscnt << "\n";
string s;
for(int i = 0; i < anscnt; i++)
s += to_string(ans[i]), s.pb(' ');
cout << s;
}
Compilation message
toy.cpp:4:0: warning: ignoring #pragma GCC comment [-Wunknown-pragmas]
#pragma GCC comment("/STACK:26666666")
toy.cpp:66:37: warning: always_inline function might not be inlinable [-Wattributes]
__attribute__((always_inline)) void solve() {
^~~~~
toy.cpp:32:37: warning: always_inline function might not be inlinable [-Wattributes]
__attribute__((always_inline)) bool gget(int i) {
^~~~
toy.cpp:25:37: warning: always_inline function might not be inlinable [-Wattributes]
__attribute__((always_inline)) void sset(int i) {
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
