oj.uz

Submission #379008

# Submission time Handle Problem Language Result Execution time Memory
379008 2021-03-17T08:20:52 Z i_am_noob Nice sequence (IZhO18_sequence) C++17
100 / 100
 435 ms 32372 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define rep(n) rep1(i,n)
#define rep1(i,n) rep2(i,0,n)
#define rep2(i,a,b) for(int i=a; i<b; ++i)
#define rep3(i,a,b) for(int i=a; i>=b; --i)
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define pow2(x) (1ll<<(x))
#define pb push_back

#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&... y){cerr << x << ' ',_do(y...);}
#else
#define bug(...) 826
#endif

const int maxn=200005;
const int mod=1000000007;
int t,n,m,neg,pos,cnt1,cnt2,cnt3,cnt4;
string str;
vector<int> vec;

void solve(int n, int m){
    if(n%m==0){
        rep(n-1) str+='1';
        return;
    }
    solve(m,n%m);
    bool flag=0;
    for(auto c: str) if(c=='0') flag=1;
    if(!flag){
        rep(n/m){
            str+='0';
            rep1(j,m-1) str+='1';
        }
        return;
    }
    string str2;
    rep(m) str2+=str[i];
    reverse(all(str2));
    rep(n/m) str+=str2;
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef i_am_noob
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    freopen("output2.txt","w",stderr);
    #endif
    cin >> t;
    while(t--){
        bug(t);
        cin >> n >> m;
        if(n%m==0){
            cout << n-1 << "\n";
            rep(n-1) cout << "1 ";
            cout << "\n";
            continue;
        }
        if(m%n==0){
            cout << m-1 << "\n";
            rep(m-1) cout << "-1 ";
            cout << "\n";
            continue;
        }
        neg=n,pos=m;
        str.clear();
        if(n<m) swap(n,m);
        solve(n,m);
        cnt1=cnt2=cnt3=cnt4=0;
        rep(n){
            if(str[i]=='1') cnt1++;
            else cnt2++;
        }
        rep(m){
            if(str[i]=='1') cnt3++;
            else cnt4++;
        }
        vec.clear();
        for(auto c: str){
            if(c=='1') vec.pb(cnt2+cnt4);
            else vec.pb(-cnt1-cnt3);
        }
        if(neg<pos){
            int k=0;
            rep(neg) k+=vec[i];
            if(k>0) for(auto& i: vec) i*=-1;
        }
        else{
            int k=0;
            rep(pos) k+=vec[i];
            if(k<0) for(auto& i: vec) i*=-1;
        }
        cout << sz(vec) << "\n";
        for(auto i: vec) cout << i << ' ';
        cout << "\n";
    }
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 | #define bug(...) 826
      |                  ^~~
sequence.cpp:58:9: note: in expansion of macro 'bug'
   58 |         bug(t);
      |         ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 0 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 2 ms 492 KB Ok
7 Correct 10 ms 876 KB Ok
8 Correct 3 ms 620 KB Ok
9 Correct 7 ms 1004 KB Ok
10 Correct 6 ms 748 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 512 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 102 ms 4844 KB Ok
7 Correct 81 ms 4444 KB Ok
8 Correct 141 ms 6648 KB Ok
9 Correct 102 ms 6876 KB Ok
10 Correct 72 ms 3040 KB Ok
11 Correct 97 ms 5872 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 1 ms 364 KB Ok
19 Correct 1 ms 364 KB Ok
20 Correct 1 ms 364 KB Ok
21 Correct 1 ms 364 KB Ok
22 Correct 1 ms 364 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 2 ms 492 KB Ok
25 Correct 2 ms 492 KB Ok
26 Correct 2 ms 492 KB Ok
27 Correct 2 ms 492 KB Ok
28 Correct 2 ms 492 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 2 ms 492 KB Ok
31 Correct 3 ms 492 KB Ok
32 Correct 2 ms 492 KB Ok
33 Correct 2 ms 492 KB Ok
34 Correct 4 ms 492 KB Ok
35 Correct 4 ms 620 KB Ok
36 Correct 4 ms 620 KB Ok
37 Correct 4 ms 620 KB Ok
38 Correct 4 ms 620 KB Ok
39 Correct 4 ms 492 KB Ok
40 Correct 6 ms 620 KB Ok
41 Correct 4 ms 620 KB Ok
42 Correct 4 ms 620 KB Ok
43 Correct 4 ms 620 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 0 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 2 ms 492 KB Ok
19 Correct 10 ms 876 KB Ok
20 Correct 3 ms 620 KB Ok
21 Correct 7 ms 1004 KB Ok
22 Correct 6 ms 748 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 2 ms 492 KB Ok
35 Correct 2 ms 492 KB Ok
36 Correct 2 ms 492 KB Ok
37 Correct 2 ms 492 KB Ok
38 Correct 2 ms 492 KB Ok
39 Correct 1 ms 364 KB Ok
40 Correct 2 ms 492 KB Ok
41 Correct 3 ms 492 KB Ok
42 Correct 2 ms 492 KB Ok
43 Correct 2 ms 492 KB Ok
44 Correct 4 ms 492 KB Ok
45 Correct 4 ms 620 KB Ok
46 Correct 4 ms 620 KB Ok
47 Correct 4 ms 620 KB Ok
48 Correct 4 ms 620 KB Ok
49 Correct 4 ms 492 KB Ok
50 Correct 6 ms 620 KB Ok
51 Correct 4 ms 620 KB Ok
52 Correct 4 ms 620 KB Ok
53 Correct 4 ms 620 KB Ok
54 Correct 57 ms 3384 KB Ok
55 Correct 89 ms 3556 KB Ok
56 Correct 68 ms 3620 KB Ok
57 Correct 48 ms 2788 KB Ok
58 Correct 75 ms 3108 KB Ok
59 Correct 58 ms 2752 KB Ok
60 Correct 46 ms 2596 KB Ok
61 Correct 56 ms 2684 KB Ok
62 Correct 75 ms 3620 KB Ok
63 Correct 62 ms 3108 KB Ok
64 Correct 70 ms 3812 KB Ok
65 Correct 67 ms 3236 KB Ok
66 Correct 56 ms 2980 KB Ok
67 Correct 44 ms 2916 KB Ok
68 Correct 61 ms 2980 KB Ok
69 Correct 109 ms 7652 KB Ok
70 Correct 114 ms 8312 KB Ok
71 Correct 102 ms 7652 KB Ok
72 Correct 108 ms 7524 KB Ok
73 Correct 117 ms 7652 KB Ok
74 Correct 103 ms 7396 KB Ok
75 Correct 103 ms 7140 KB Ok
76 Correct 106 ms 7780 KB Ok
77 Correct 102 ms 7460 KB Ok
78 Correct 105 ms 7524 KB Ok
79 Correct 115 ms 7908 KB Ok
80 Correct 107 ms 7524 KB Ok
81 Correct 106 ms 7652 KB Ok
82 Correct 105 ms 7524 KB Ok
83 Correct 101 ms 7260 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 0 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 2 ms 492 KB Ok
19 Correct 10 ms 876 KB Ok
20 Correct 3 ms 620 KB Ok
21 Correct 7 ms 1004 KB Ok
22 Correct 6 ms 748 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 512 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 1 ms 364 KB Ok
39 Correct 102 ms 4844 KB Ok
40 Correct 81 ms 4444 KB Ok
41 Correct 141 ms 6648 KB Ok
42 Correct 102 ms 6876 KB Ok
43 Correct 72 ms 3040 KB Ok
44 Correct 97 ms 5872 KB Ok
45 Correct 2 ms 492 KB Ok
46 Correct 2 ms 492 KB Ok
47 Correct 2 ms 492 KB Ok
48 Correct 2 ms 492 KB Ok
49 Correct 2 ms 492 KB Ok
50 Correct 1 ms 364 KB Ok
51 Correct 2 ms 492 KB Ok
52 Correct 3 ms 492 KB Ok
53 Correct 2 ms 492 KB Ok
54 Correct 2 ms 492 KB Ok
55 Correct 4 ms 492 KB Ok
56 Correct 4 ms 620 KB Ok
57 Correct 4 ms 620 KB Ok
58 Correct 4 ms 620 KB Ok
59 Correct 4 ms 620 KB Ok
60 Correct 4 ms 492 KB Ok
61 Correct 6 ms 620 KB Ok
62 Correct 4 ms 620 KB Ok
63 Correct 4 ms 620 KB Ok
64 Correct 4 ms 620 KB Ok
65 Correct 57 ms 3384 KB Ok
66 Correct 89 ms 3556 KB Ok
67 Correct 68 ms 3620 KB Ok
68 Correct 48 ms 2788 KB Ok
69 Correct 75 ms 3108 KB Ok
70 Correct 58 ms 2752 KB Ok
71 Correct 46 ms 2596 KB Ok
72 Correct 56 ms 2684 KB Ok
73 Correct 75 ms 3620 KB Ok
74 Correct 62 ms 3108 KB Ok
75 Correct 70 ms 3812 KB Ok
76 Correct 67 ms 3236 KB Ok
77 Correct 56 ms 2980 KB Ok
78 Correct 44 ms 2916 KB Ok
79 Correct 61 ms 2980 KB Ok
80 Correct 109 ms 7652 KB Ok
81 Correct 114 ms 8312 KB Ok
82 Correct 102 ms 7652 KB Ok
83 Correct 108 ms 7524 KB Ok
84 Correct 117 ms 7652 KB Ok
85 Correct 103 ms 7396 KB Ok
86 Correct 103 ms 7140 KB Ok
87 Correct 106 ms 7780 KB Ok
88 Correct 102 ms 7460 KB Ok
89 Correct 105 ms 7524 KB Ok
90 Correct 115 ms 7908 KB Ok
91 Correct 107 ms 7524 KB Ok
92 Correct 106 ms 7652 KB Ok
93 Correct 105 ms 7524 KB Ok
94 Correct 101 ms 7260 KB Ok
95 Correct 115 ms 7404 KB Ok
96 Correct 200 ms 10228 KB Ok
97 Correct 217 ms 9464 KB Ok
98 Correct 153 ms 7596 KB Ok
99 Correct 178 ms 9392 KB Ok
100 Correct 204 ms 8796 KB Ok
101 Correct 206 ms 8692 KB Ok
102 Correct 173 ms 9140 KB Ok
103 Correct 178 ms 8640 KB Ok
104 Correct 218 ms 10228 KB Ok
105 Correct 217 ms 10552 KB Ok
106 Correct 146 ms 9916 KB Ok
107 Correct 194 ms 9844 KB Ok
108 Correct 228 ms 11364 KB Ok
109 Correct 191 ms 10896 KB Ok
110 Correct 431 ms 30440 KB Ok
111 Correct 418 ms 32116 KB Ok
112 Correct 418 ms 31740 KB Ok
113 Correct 416 ms 31212 KB Ok
114 Correct 435 ms 32244 KB Ok
115 Correct 422 ms 31348 KB Ok
116 Correct 425 ms 32372 KB Ok
117 Correct 419 ms 31368 KB Ok
118 Correct 417 ms 31736 KB Ok
119 Correct 420 ms 31092 KB Ok
120 Correct 434 ms 31132 KB Ok
121 Correct 415 ms 29068 KB Ok
122 Correct 417 ms 31472 KB Ok
123 Correct 420 ms 32140 KB Ok
124 Correct 428 ms 30700 KB Ok
125 Correct 385 ms 14580 KB Ok