oj.uz

Submission #543340

# Submission time Handle Problem Language Result Execution time Memory
543340 2022-03-30T10:16:26 Z eecs Present (RMI21_present) C++17
100 / 100
 2137 ms 4320 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

int T, K, lim[1 << 19], mark[38], cnt[1 << 18];
bool ok1[1 << 19], ok2[1 << 18];

int main() {
    for (int i = 0; i < 1 << 19; i++) {
        ok1[i] = 1, lim[i] = (1 << 18) - 1;
        for (int j = 0; j < 19 && ok1[i]; j++) if (i >> j & 1) {
            for (int k = j + 1; k < 19; k++) if (i >> k & 1) {
                ok1[i] &= i >> (__gcd(2 * j + 1, 2 * k + 1) / 2) & 1;
            }
            for (int k = 0; k < 18; k++) {
                if (!(i >> (__gcd(2 * j + 1, 2 * k + 2) / 2) & 1)) lim[i] &= ~(1 << k);
            }
        }
    }
    for (int i = 0; i < 1 << 18; i++) {
        ok2[i] = 1;
        for (int j = 0; j < 18 && ok2[i]; j++) if (i >> j & 1) {
            for (int k = j + 1; k < 18; k++) if (i >> k & 1) {
                ok2[i] &= i >> (__gcd(2 * j + 2, 2 * k + 2) / 2 - 1) & 1;
            }
        }
    }
    auto calc = [&]() {
        copy(ok2, ok2 + (1 << 18), cnt);
        for (int i = 0; i < 1 << 18; i++) {
            for (int j = 0; j < 18 && cnt[i]; j++) {
                if (~mark[2 * j + 2] && mark[2 * j + 2] ^ (i >> j & 1)) cnt[i] = 0;
            }
        }
        for (int i = 0; i < 18; i++) {
            for (int j = 0; j < 1 << 18; j++) {
                if (j >> i & 1) cnt[j] += cnt[j ^ (1 << i)];
            }
        }
        long long s = 0;
        for (int i = 0; i < 1 << 19; i++) if (ok1[i]) {
            bool flag = 1;
            for (int j = 0; j < 19 && flag; j++) {
                if (~mark[2 * j + 1] && mark[2 * j + 1] ^ (i >> j & 1)) flag = 0;
            }
            if (flag) s += cnt[lim[i]];
        }
        return s;
    };
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &K), K++;
        memset(mark, -1, sizeof(mark));
        vector<int> res;
        for (int i = 37; i; i--) {
            mark[i] = 0;
            long long t = calc();
            if (t < K) mark[i] = 1, K -= t, res.push_back(i);
        }
        printf("%d", res.size());
        reverse(res.begin(), res.end());
        for (int x : res) printf(" %d", x);
        putchar('\n');
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:60:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   60 |         printf("%d", res.size());
      |                 ~^   ~~~~~~~~~~
      |                  |           |
      |                  int         std::vector<int>::size_type {aka long unsigned int}
      |                 %ld
Main.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~
Main.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d", &K), K++;
      |         ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1950 ms 4232 KB Output is correct
2 Correct 1923 ms 4164 KB Output is correct
3 Correct 1926 ms 4136 KB Output is correct
4 Correct 1932 ms 4128 KB Output is correct
5 Correct 1977 ms 4128 KB Output is correct
6 Correct 1927 ms 4296 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1950 ms 4232 KB Output is correct
2 Correct 1923 ms 4164 KB Output is correct
3 Correct 1926 ms 4136 KB Output is correct
4 Correct 1932 ms 4128 KB Output is correct
5 Correct 1977 ms 4128 KB Output is correct
6 Correct 1927 ms 4296 KB Output is correct
7 Correct 1939 ms 4320 KB Output is correct
8 Correct 1921 ms 4124 KB Output is correct
9 Correct 1937 ms 4128 KB Output is correct
10 Correct 1965 ms 4212 KB Output is correct
11 Correct 1953 ms 4208 KB Output is correct
12 Correct 1929 ms 4128 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1950 ms 4232 KB Output is correct
2 Correct 1923 ms 4164 KB Output is correct
3 Correct 1926 ms 4136 KB Output is correct
4 Correct 1932 ms 4128 KB Output is correct
5 Correct 1977 ms 4128 KB Output is correct
6 Correct 1927 ms 4296 KB Output is correct
7 Correct 1939 ms 4320 KB Output is correct
8 Correct 1921 ms 4124 KB Output is correct
9 Correct 1937 ms 4128 KB Output is correct
10 Correct 1965 ms 4212 KB Output is correct
11 Correct 1953 ms 4208 KB Output is correct
12 Correct 1929 ms 4128 KB Output is correct
13 Correct 1995 ms 4212 KB Output is correct
14 Correct 1973 ms 4140 KB Output is correct
15 Correct 1958 ms 4132 KB Output is correct
16 Correct 1958 ms 4128 KB Output is correct
17 Correct 2011 ms 4124 KB Output is correct
18 Correct 2054 ms 4212 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1950 ms 4232 KB Output is correct
2 Correct 1923 ms 4164 KB Output is correct
3 Correct 1926 ms 4136 KB Output is correct
4 Correct 1932 ms 4128 KB Output is correct
5 Correct 1977 ms 4128 KB Output is correct
6 Correct 1927 ms 4296 KB Output is correct
7 Correct 1939 ms 4320 KB Output is correct
8 Correct 1921 ms 4124 KB Output is correct
9 Correct 1937 ms 4128 KB Output is correct
10 Correct 1965 ms 4212 KB Output is correct
11 Correct 1953 ms 4208 KB Output is correct
12 Correct 1929 ms 4128 KB Output is correct
13 Correct 1995 ms 4212 KB Output is correct
14 Correct 1973 ms 4140 KB Output is correct
15 Correct 1958 ms 4132 KB Output is correct
16 Correct 1958 ms 4128 KB Output is correct
17 Correct 2011 ms 4124 KB Output is correct
18 Correct 2054 ms 4212 KB Output is correct
19 Correct 2099 ms 4128 KB Output is correct
20 Correct 2072 ms 4252 KB Output is correct
21 Correct 2053 ms 4152 KB Output is correct
22 Correct 2090 ms 4132 KB Output is correct
23 Correct 2102 ms 4128 KB Output is correct
24 Correct 2102 ms 4208 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1950 ms 4232 KB Output is correct
2 Correct 1923 ms 4164 KB Output is correct
3 Correct 1926 ms 4136 KB Output is correct
4 Correct 1932 ms 4128 KB Output is correct
5 Correct 1977 ms 4128 KB Output is correct
6 Correct 1927 ms 4296 KB Output is correct
7 Correct 1939 ms 4320 KB Output is correct
8 Correct 1921 ms 4124 KB Output is correct
9 Correct 1937 ms 4128 KB Output is correct
10 Correct 1965 ms 4212 KB Output is correct
11 Correct 1953 ms 4208 KB Output is correct
12 Correct 1929 ms 4128 KB Output is correct
13 Correct 1995 ms 4212 KB Output is correct
14 Correct 1973 ms 4140 KB Output is correct
15 Correct 1958 ms 4132 KB Output is correct
16 Correct 1958 ms 4128 KB Output is correct
17 Correct 2011 ms 4124 KB Output is correct
18 Correct 2054 ms 4212 KB Output is correct
19 Correct 2099 ms 4128 KB Output is correct
20 Correct 2072 ms 4252 KB Output is correct
21 Correct 2053 ms 4152 KB Output is correct
22 Correct 2090 ms 4132 KB Output is correct
23 Correct 2102 ms 4128 KB Output is correct
24 Correct 2102 ms 4208 KB Output is correct
25 Correct 2137 ms 4132 KB Output is correct
26 Correct 1987 ms 4160 KB Output is correct
27 Correct 2015 ms 4076 KB Output is correct
28 Correct 1989 ms 4236 KB Output is correct
29 Correct 1984 ms 4280 KB Output is correct
30 Correct 1988 ms 4128 KB Output is correct