제출 #543337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543337		eecs	Present (RMI21_present)	C++17	100 / 100	2325 ms	4344 KiB

Main

#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() {
    // odd
    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);
            }
        }
    }
    // even
    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 = [&]() {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < 1 << 18; i++) if (ok2[i]) {
            bool flag = 1;
            for (int j = 0; j < 18; j++) {
                if (~mark[2 * j + 2] && mark[2 * j + 2] ^ (i >> j & 1)) flag = 0;
            }
            if (flag) cnt[i]++;
        }
        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; 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 41 / 41
• Subtask 4: 14 / 14
• Subtask 5: 16 / 16