oj.uz

Submission #475639

# Submission time Handle Problem Language Result Execution time Memory
475639 2021-09-23T14:30:41 Z NhatMinh0208 Nice sequence (IZhO18_sequence) C++14
100 / 100
 1506 ms 76872 KB 
#ifndef CPL_TEMPLATE
#define CPL_TEMPLATE
/*
	Normie's Template v2.5
	Changes:
    Added warning against using pragmas on USACO.
*/
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;

//Pragmas (Comment out these three lines if you're submitting in szkopul or USACO.)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0)
#define nfio cin.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
template<typename T>
__attribute__((always_inline)) void chkmin(T& a, const T& b) {
    a=(a<b)?a:b;
}

template<typename T>
__attribute__((always_inline)) void chkmax(T& a, const T& b) {
    a=(a>b)?a:b;
}
 
//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;

// Binpow and stuff
ll BOW(ll a, ll x, ll p)
{
	if (!x) return 1;
	ll res=BOW(a,x/2,p);
	res*=res;
	res%=p;
	if (x%2) res*=a;
	return res%p;
}
ll INV(ll a, ll p)
{
	return BOW(a,p-2,p);
}
//---------END-------//
#endif
vector<int> gtu[400001],gtd[400001],vec;
int n,m,i,j,k,t,t1,u,v,a,b;
int deg[400001];
int fin[400001];
int main()
{
	fio;
    cin>>t;
    for (t1=0;t1<t;t1++) {
        cin>>n>>m;
        k=m+n-__gcd(m,n)-1;
        cout<<k<<"\n";
        if (k) {
            for (i=0;i<=k;i++) {
                gtu[i].clear();
                gtd[i].clear();
            }
            for (i=0;i+n<=k;i++) {
                gtd[i].push_back(i+n);
                gtu[i+n].push_back(i);
                // cout<<i+n<<' '<<i<<endl;
            }
            for (i=0;i+m<=k;i++) {
                gtu[i].push_back(i+m);
                gtd[i+m].push_back(i);
                // cout<<i<<' '<<i+m<<endl;
            }
            vec.clear();
            for (i=0;i<=k;i++) {
                deg[i]=gtd[i].size();
                if (!deg[i]) vec.push_back(i);
            }
            u=0;
            while(vec.size()) {
                v=vec.back();
                // cout<<v<<' ';
                vec.pop_back();
                fin[v]=u;
                u++;
                for (auto g  : gtu[v]) {
                    deg[g]--;
                    if (!deg[g]) vec.push_back(g);
                }            
            }
            // cout<<endl;        
            // for (i=0;i<=k;i++) {
                // cout<<fin[i]<<' ';
            // }
            // cout<<endl;        
            for (i=1;i<=k;i++) {
                cout<<fin[i]-fin[i-1]<<' ';
            }
            cout<<endl;        
        }
    }
}
// N;

Compilation message

sequence.cpp:23: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
   23 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19020 KB Ok
2 Correct 11 ms 19020 KB Ok
3 Correct 10 ms 19104 KB Ok
4 Correct 9 ms 19108 KB Ok
5 Correct 11 ms 19108 KB Ok
6 Correct 10 ms 19020 KB Ok
7 Correct 11 ms 19036 KB Ok
8 Correct 10 ms 19020 KB Ok
9 Correct 9 ms 19020 KB Ok
10 Correct 9 ms 19020 KB Ok
11 Correct 10 ms 19044 KB Ok
12 Correct 12 ms 19020 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19148 KB Ok
2 Correct 10 ms 19108 KB Ok
3 Correct 10 ms 19104 KB Ok
4 Correct 9 ms 19108 KB Ok
5 Correct 10 ms 19108 KB Ok
6 Correct 12 ms 19312 KB Ok
7 Correct 20 ms 20100 KB Ok
8 Correct 16 ms 19556 KB Ok
9 Correct 23 ms 20304 KB Ok
10 Correct 20 ms 19788 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19020 KB Ok
2 Correct 10 ms 19116 KB Ok
3 Correct 10 ms 19080 KB Ok
4 Correct 10 ms 19108 KB Ok
5 Correct 11 ms 19072 KB Ok
6 Correct 10 ms 19064 KB Ok
7 Correct 10 ms 19020 KB Ok
8 Correct 10 ms 19108 KB Ok
9 Correct 11 ms 19020 KB Ok
10 Correct 10 ms 19020 KB Ok
11 Correct 9 ms 19096 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19020 KB Ok
2 Correct 10 ms 19080 KB Ok
3 Correct 12 ms 19012 KB Ok
4 Correct 11 ms 19020 KB Ok
5 Correct 10 ms 19104 KB Ok
6 Correct 130 ms 35220 KB Ok
7 Correct 107 ms 35148 KB Ok
8 Correct 204 ms 39136 KB Ok
9 Correct 153 ms 36548 KB Ok
10 Correct 99 ms 30204 KB Ok
11 Correct 151 ms 37748 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19020 KB Ok
2 Correct 11 ms 19020 KB Ok
3 Correct 10 ms 19104 KB Ok
4 Correct 9 ms 19108 KB Ok
5 Correct 11 ms 19108 KB Ok
6 Correct 10 ms 19020 KB Ok
7 Correct 11 ms 19036 KB Ok
8 Correct 10 ms 19020 KB Ok
9 Correct 9 ms 19020 KB Ok
10 Correct 9 ms 19020 KB Ok
11 Correct 10 ms 19044 KB Ok
12 Correct 12 ms 19020 KB Ok
13 Correct 10 ms 19020 KB Ok
14 Correct 10 ms 19116 KB Ok
15 Correct 10 ms 19080 KB Ok
16 Correct 10 ms 19108 KB Ok
17 Correct 11 ms 19072 KB Ok
18 Correct 10 ms 19064 KB Ok
19 Correct 10 ms 19020 KB Ok
20 Correct 10 ms 19108 KB Ok
21 Correct 11 ms 19020 KB Ok
22 Correct 10 ms 19020 KB Ok
23 Correct 9 ms 19096 KB Ok
24 Correct 11 ms 19360 KB Ok
25 Correct 12 ms 19404 KB Ok
26 Correct 13 ms 19276 KB Ok
27 Correct 12 ms 19364 KB Ok
28 Correct 11 ms 19276 KB Ok
29 Correct 17 ms 19276 KB Ok
30 Correct 12 ms 19236 KB Ok
31 Correct 12 ms 19404 KB Ok
32 Correct 13 ms 19360 KB Ok
33 Correct 12 ms 19364 KB Ok
34 Correct 14 ms 19492 KB Ok
35 Correct 15 ms 19420 KB Ok
36 Correct 14 ms 19532 KB Ok
37 Correct 14 ms 19548 KB Ok
38 Correct 14 ms 19552 KB Ok
39 Correct 14 ms 19448 KB Ok
40 Correct 16 ms 19548 KB Ok
41 Correct 14 ms 19604 KB Ok
42 Correct 18 ms 19476 KB Ok
43 Correct 14 ms 19492 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19020 KB Ok
2 Correct 11 ms 19020 KB Ok
3 Correct 10 ms 19104 KB Ok
4 Correct 9 ms 19108 KB Ok
5 Correct 11 ms 19108 KB Ok
6 Correct 10 ms 19020 KB Ok
7 Correct 11 ms 19036 KB Ok
8 Correct 10 ms 19020 KB Ok
9 Correct 9 ms 19020 KB Ok
10 Correct 9 ms 19020 KB Ok
11 Correct 10 ms 19044 KB Ok
12 Correct 12 ms 19020 KB Ok
13 Correct 9 ms 19148 KB Ok
14 Correct 10 ms 19108 KB Ok
15 Correct 10 ms 19104 KB Ok
16 Correct 9 ms 19108 KB Ok
17 Correct 10 ms 19108 KB Ok
18 Correct 12 ms 19312 KB Ok
19 Correct 20 ms 20100 KB Ok
20 Correct 16 ms 19556 KB Ok
21 Correct 23 ms 20304 KB Ok
22 Correct 20 ms 19788 KB Ok
23 Correct 10 ms 19020 KB Ok
24 Correct 10 ms 19116 KB Ok
25 Correct 10 ms 19080 KB Ok
26 Correct 10 ms 19108 KB Ok
27 Correct 11 ms 19072 KB Ok
28 Correct 10 ms 19064 KB Ok
29 Correct 10 ms 19020 KB Ok
30 Correct 10 ms 19108 KB Ok
31 Correct 11 ms 19020 KB Ok
32 Correct 10 ms 19020 KB Ok
33 Correct 9 ms 19096 KB Ok
34 Correct 11 ms 19360 KB Ok
35 Correct 12 ms 19404 KB Ok
36 Correct 13 ms 19276 KB Ok
37 Correct 12 ms 19364 KB Ok
38 Correct 11 ms 19276 KB Ok
39 Correct 17 ms 19276 KB Ok
40 Correct 12 ms 19236 KB Ok
41 Correct 12 ms 19404 KB Ok
42 Correct 13 ms 19360 KB Ok
43 Correct 12 ms 19364 KB Ok
44 Correct 14 ms 19492 KB Ok
45 Correct 15 ms 19420 KB Ok
46 Correct 14 ms 19532 KB Ok
47 Correct 14 ms 19548 KB Ok
48 Correct 14 ms 19552 KB Ok
49 Correct 14 ms 19448 KB Ok
50 Correct 16 ms 19548 KB Ok
51 Correct 14 ms 19604 KB Ok
52 Correct 18 ms 19476 KB Ok
53 Correct 14 ms 19492 KB Ok
54 Correct 99 ms 28264 KB Ok
55 Correct 136 ms 28716 KB Ok
56 Correct 121 ms 28824 KB Ok
57 Correct 83 ms 27252 KB Ok
58 Correct 112 ms 28148 KB Ok
59 Correct 101 ms 27748 KB Ok
60 Correct 85 ms 27072 KB Ok
61 Correct 92 ms 27876 KB Ok
62 Correct 121 ms 28484 KB Ok
63 Correct 106 ms 27476 KB Ok
64 Correct 124 ms 28484 KB Ok
65 Correct 110 ms 28428 KB Ok
66 Correct 94 ms 27952 KB Ok
67 Correct 87 ms 27580 KB Ok
68 Correct 113 ms 28220 KB Ok
69 Correct 266 ms 32312 KB Ok
70 Correct 292 ms 32688 KB Ok
71 Correct 278 ms 32708 KB Ok
72 Correct 269 ms 32192 KB Ok
73 Correct 288 ms 32680 KB Ok
74 Correct 282 ms 32640 KB Ok
75 Correct 276 ms 32356 KB Ok
76 Correct 275 ms 32292 KB Ok
77 Correct 299 ms 32752 KB Ok
78 Correct 257 ms 32136 KB Ok
79 Correct 295 ms 32596 KB Ok
80 Correct 315 ms 32740 KB Ok
81 Correct 261 ms 32560 KB Ok
82 Correct 280 ms 32580 KB Ok
83 Correct 284 ms 32644 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19020 KB Ok
2 Correct 11 ms 19020 KB Ok
3 Correct 10 ms 19104 KB Ok
4 Correct 9 ms 19108 KB Ok
5 Correct 11 ms 19108 KB Ok
6 Correct 10 ms 19020 KB Ok
7 Correct 11 ms 19036 KB Ok
8 Correct 10 ms 19020 KB Ok
9 Correct 9 ms 19020 KB Ok
10 Correct 9 ms 19020 KB Ok
11 Correct 10 ms 19044 KB Ok
12 Correct 12 ms 19020 KB Ok
13 Correct 9 ms 19148 KB Ok
14 Correct 10 ms 19108 KB Ok
15 Correct 10 ms 19104 KB Ok
16 Correct 9 ms 19108 KB Ok
17 Correct 10 ms 19108 KB Ok
18 Correct 12 ms 19312 KB Ok
19 Correct 20 ms 20100 KB Ok
20 Correct 16 ms 19556 KB Ok
21 Correct 23 ms 20304 KB Ok
22 Correct 20 ms 19788 KB Ok
23 Correct 10 ms 19020 KB Ok
24 Correct 10 ms 19116 KB Ok
25 Correct 10 ms 19080 KB Ok
26 Correct 10 ms 19108 KB Ok
27 Correct 11 ms 19072 KB Ok
28 Correct 10 ms 19064 KB Ok
29 Correct 10 ms 19020 KB Ok
30 Correct 10 ms 19108 KB Ok
31 Correct 11 ms 19020 KB Ok
32 Correct 10 ms 19020 KB Ok
33 Correct 9 ms 19096 KB Ok
34 Correct 11 ms 19020 KB Ok
35 Correct 10 ms 19080 KB Ok
36 Correct 12 ms 19012 KB Ok
37 Correct 11 ms 19020 KB Ok
38 Correct 10 ms 19104 KB Ok
39 Correct 130 ms 35220 KB Ok
40 Correct 107 ms 35148 KB Ok
41 Correct 204 ms 39136 KB Ok
42 Correct 153 ms 36548 KB Ok
43 Correct 99 ms 30204 KB Ok
44 Correct 151 ms 37748 KB Ok
45 Correct 11 ms 19360 KB Ok
46 Correct 12 ms 19404 KB Ok
47 Correct 13 ms 19276 KB Ok
48 Correct 12 ms 19364 KB Ok
49 Correct 11 ms 19276 KB Ok
50 Correct 17 ms 19276 KB Ok
51 Correct 12 ms 19236 KB Ok
52 Correct 12 ms 19404 KB Ok
53 Correct 13 ms 19360 KB Ok
54 Correct 12 ms 19364 KB Ok
55 Correct 14 ms 19492 KB Ok
56 Correct 15 ms 19420 KB Ok
57 Correct 14 ms 19532 KB Ok
58 Correct 14 ms 19548 KB Ok
59 Correct 14 ms 19552 KB Ok
60 Correct 14 ms 19448 KB Ok
61 Correct 16 ms 19548 KB Ok
62 Correct 14 ms 19604 KB Ok
63 Correct 18 ms 19476 KB Ok
64 Correct 14 ms 19492 KB Ok
65 Correct 99 ms 28264 KB Ok
66 Correct 136 ms 28716 KB Ok
67 Correct 121 ms 28824 KB Ok
68 Correct 83 ms 27252 KB Ok
69 Correct 112 ms 28148 KB Ok
70 Correct 101 ms 27748 KB Ok
71 Correct 85 ms 27072 KB Ok
72 Correct 92 ms 27876 KB Ok
73 Correct 121 ms 28484 KB Ok
74 Correct 106 ms 27476 KB Ok
75 Correct 124 ms 28484 KB Ok
76 Correct 110 ms 28428 KB Ok
77 Correct 94 ms 27952 KB Ok
78 Correct 87 ms 27580 KB Ok
79 Correct 113 ms 28220 KB Ok
80 Correct 266 ms 32312 KB Ok
81 Correct 292 ms 32688 KB Ok
82 Correct 278 ms 32708 KB Ok
83 Correct 269 ms 32192 KB Ok
84 Correct 288 ms 32680 KB Ok
85 Correct 282 ms 32640 KB Ok
86 Correct 276 ms 32356 KB Ok
87 Correct 275 ms 32292 KB Ok
88 Correct 299 ms 32752 KB Ok
89 Correct 257 ms 32136 KB Ok
90 Correct 295 ms 32596 KB Ok
91 Correct 315 ms 32740 KB Ok
92 Correct 261 ms 32560 KB Ok
93 Correct 280 ms 32580 KB Ok
94 Correct 284 ms 32644 KB Ok
95 Correct 274 ms 42864 KB Ok
96 Correct 415 ms 53592 KB Ok
97 Correct 323 ms 47368 KB Ok
98 Correct 235 ms 47584 KB Ok
99 Correct 290 ms 46652 KB Ok
100 Correct 298 ms 46760 KB Ok
101 Correct 309 ms 51136 KB Ok
102 Correct 341 ms 48424 KB Ok
103 Correct 355 ms 50104 KB Ok
104 Correct 395 ms 52516 KB Ok
105 Correct 338 ms 53084 KB Ok
106 Correct 326 ms 53236 KB Ok
107 Correct 298 ms 51976 KB Ok
108 Correct 394 ms 52460 KB Ok
109 Correct 365 ms 54736 KB Ok
110 Correct 1303 ms 74756 KB Ok
111 Correct 1400 ms 74996 KB Ok
112 Correct 1474 ms 76872 KB Ok
113 Correct 1382 ms 74744 KB Ok
114 Correct 1399 ms 76816 KB Ok
115 Correct 1483 ms 75320 KB Ok
116 Correct 1473 ms 76360 KB Ok
117 Correct 1431 ms 74268 KB Ok
118 Correct 1486 ms 76700 KB Ok
119 Correct 1418 ms 73692 KB Ok
120 Correct 1448 ms 75052 KB Ok
121 Correct 1470 ms 75468 KB Ok
122 Correct 1389 ms 75436 KB Ok
123 Correct 1506 ms 75148 KB Ok
124 Correct 1443 ms 76700 KB Ok
125 Correct 465 ms 57280 KB Ok