oj.uz

Submission #646662

# Submission time Handle Problem Language Result Execution time Memory
646662 2022-09-30T11:32:22 Z ksu2009en Present (RMI21_present) C++14
29 / 100
 3188 ms 437008 KB 
#pragma GCC optimize("O3")

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#define endl '\n'

#include <unordered_map>

using namespace std;
typedef long long ll;

ll used[10001];

ll step = 0;

bool check(vector<ll>a){
    step++;
    
    for(auto i: a){
        used[i] = step;
        
        for(auto j: a){
            if(used[__gcd(i, j)] != step)
                return false;
        }
    }
    return true;
}

int main(){
    vector<vector<ll>>d(1000009);
    
    int pos = 1;
    
    for(int num = 1; num <= 1000; num++){
        d[pos++] = {num};
        
        ll last = pos - 1;
        
        for(int j = 1; j < last; j++){
            d[pos] = d[j];
            d[pos].push_back(num);
            
            if(!check(d[pos]))
                continue;
            pos++;
            
            if(pos >= 1000001)
                break;
        }
        if(pos >= 1000001)
            break;
    }
    
    ll t;
    cin >> t;
    
    while(t--){
        ll n;
        cin >> n;
        
        cout << d[n].size() << ' ';
        for(auto i: d[n])
            cout << i << ' ';
        cout << endl;
    }
    
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3048 ms 215644 KB Output is correct
2 Correct 3073 ms 215572 KB Output is correct
3 Correct 3067 ms 215520 KB Output is correct
4 Correct 3067 ms 215784 KB Output is correct
5 Correct 3143 ms 215664 KB Output is correct
6 Correct 3082 ms 215608 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3048 ms 215644 KB Output is correct
2 Correct 3073 ms 215572 KB Output is correct
3 Correct 3067 ms 215520 KB Output is correct
4 Correct 3067 ms 215784 KB Output is correct
5 Correct 3143 ms 215664 KB Output is correct
6 Correct 3082 ms 215608 KB Output is correct
7 Correct 3083 ms 215668 KB Output is correct
8 Correct 3064 ms 215684 KB Output is correct
9 Correct 3062 ms 215796 KB Output is correct
10 Correct 3041 ms 215624 KB Output is correct
11 Correct 3052 ms 215500 KB Output is correct
12 Correct 3039 ms 215672 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3048 ms 215644 KB Output is correct
2 Correct 3073 ms 215572 KB Output is correct
3 Correct 3067 ms 215520 KB Output is correct
4 Correct 3067 ms 215784 KB Output is correct
5 Correct 3143 ms 215664 KB Output is correct
6 Correct 3082 ms 215608 KB Output is correct
7 Correct 3083 ms 215668 KB Output is correct
8 Correct 3064 ms 215684 KB Output is correct
9 Correct 3062 ms 215796 KB Output is correct
10 Correct 3041 ms 215624 KB Output is correct
11 Correct 3052 ms 215500 KB Output is correct
12 Correct 3039 ms 215672 KB Output is correct
13 Runtime error 3188 ms 437008 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3048 ms 215644 KB Output is correct
2 Correct 3073 ms 215572 KB Output is correct
3 Correct 3067 ms 215520 KB Output is correct
4 Correct 3067 ms 215784 KB Output is correct
5 Correct 3143 ms 215664 KB Output is correct
6 Correct 3082 ms 215608 KB Output is correct
7 Correct 3083 ms 215668 KB Output is correct
8 Correct 3064 ms 215684 KB Output is correct
9 Correct 3062 ms 215796 KB Output is correct
10 Correct 3041 ms 215624 KB Output is correct
11 Correct 3052 ms 215500 KB Output is correct
12 Correct 3039 ms 215672 KB Output is correct
13 Runtime error 3188 ms 437008 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3048 ms 215644 KB Output is correct
2 Correct 3073 ms 215572 KB Output is correct
3 Correct 3067 ms 215520 KB Output is correct
4 Correct 3067 ms 215784 KB Output is correct
5 Correct 3143 ms 215664 KB Output is correct
6 Correct 3082 ms 215608 KB Output is correct
7 Correct 3083 ms 215668 KB Output is correct
8 Correct 3064 ms 215684 KB Output is correct
9 Correct 3062 ms 215796 KB Output is correct
10 Correct 3041 ms 215624 KB Output is correct
11 Correct 3052 ms 215500 KB Output is correct
12 Correct 3039 ms 215672 KB Output is correct
13 Runtime error 3188 ms 437008 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -