oj.uz

Submission #737139

# Submission time Handle Problem Language Result Execution time Memory
737139 2023-05-06T17:12:48 Z puppy Present (RMI21_present) C++17
29 / 100
 4000 ms 292 KB 
#include <iostream>
#include <numeric>
using namespace std;
int g[41][41];
long long get_closed(long long ind)
{
    long long ans = ind;
    for (int i = 40; i >= 1; i--) {
        if (ans & 1LL << i-1) {
            for (int j = i-1; j >= 1; j--) {
                if (ans & 1LL << j-1) {
                    ans |= 1LL << g[i][j]-1;
                }
            }
        }
    }
    return ans;
}
long long get_next(long long cur)
{
    long long bef = get_closed(cur);
    for (int i = 1;; i++) {
        if (!(bef & (1LL << i-1))) {
            for (int j = 1; j < i; j++) {
                if (cur & (1LL << j-1)) cur -= 1LL << j-1;
            }
            cur += 1LL << i-1;
            return cur;
        }
    }
}
int popcount(long long id)
{
    int cnt = 0;
    for (int i = 0; i < 40; i++) {
        if (id & (1LL << i)) cnt++;
    }
    return cnt;
}
void print_set(long long id)
{
    cout << popcount(id) << ' ';
    for (int i = 1; i <= 40; i++) {
        if (id & (1LL << i-1)) cout << i << ' ';
    }
    cout << '\n';
}
int main()
{
    for (int i = 1; i <= 40; i++) {
        for (int j = 1; j <= 40; j++) {
            g[i][j] = gcd(i, j);
        }
    }
    int T; cin >> T;
    while (T--) {
        int K; cin >> K;
        long long cur = 0;
        for (int i = 1; i <= K; i++) cur = get_next(cur);
        print_set(get_closed(cur));
    }
}

Compilation message

Main.cpp: In function 'long long int get_closed(long long int)':
Main.cpp:9:27: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    9 |         if (ans & 1LL << i-1) {
      |                          ~^~
Main.cpp:11:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   11 |                 if (ans & 1LL << j-1) {
      |                                  ~^~
Main.cpp:12:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   12 |                     ans |= 1LL << g[i][j]-1;
      |                                   ~~~~~~~^~
Main.cpp: In function 'long long int get_next(long long int)':
Main.cpp:23:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   23 |         if (!(bef & (1LL << i-1))) {
      |                             ~^~
Main.cpp:25:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |                 if (cur & (1LL << j-1)) cur -= 1LL << j-1;
      |                                   ~^~
Main.cpp:25:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |                 if (cur & (1LL << j-1)) cur -= 1LL << j-1;
      |                                                       ~^~
Main.cpp:27:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |             cur += 1LL << i-1;
      |                           ~^~
Main.cpp: In function 'void print_set(long long int)':
Main.cpp:44:27: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |         if (id & (1LL << i-1)) cout << i << ' ';
      |                          ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 932 ms 288 KB Output is correct
8 Correct 1380 ms 280 KB Output is correct
9 Correct 1069 ms 212 KB Output is correct
10 Correct 1281 ms 284 KB Output is correct
11 Correct 604 ms 212 KB Output is correct
12 Correct 1190 ms 212 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 932 ms 288 KB Output is correct
8 Correct 1380 ms 280 KB Output is correct
9 Correct 1069 ms 212 KB Output is correct
10 Correct 1281 ms 284 KB Output is correct
11 Correct 604 ms 212 KB Output is correct
12 Correct 1190 ms 212 KB Output is correct
13 Execution timed out 4058 ms 212 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 932 ms 288 KB Output is correct
8 Correct 1380 ms 280 KB Output is correct
9 Correct 1069 ms 212 KB Output is correct
10 Correct 1281 ms 284 KB Output is correct
11 Correct 604 ms 212 KB Output is correct
12 Correct 1190 ms 212 KB Output is correct
13 Execution timed out 4058 ms 212 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 932 ms 288 KB Output is correct
8 Correct 1380 ms 280 KB Output is correct
9 Correct 1069 ms 212 KB Output is correct
10 Correct 1281 ms 284 KB Output is correct
11 Correct 604 ms 212 KB Output is correct
12 Correct 1190 ms 212 KB Output is correct
13 Execution timed out 4058 ms 212 KB Time limit exceeded
14 Halted 0 ms 0 KB -