oj.uz

Submission #646663

# Submission time Handle Problem Language Result Execution time Memory
646663 2022-09-30T11:33:23 Z ksu2009en Present (RMI21_present) C++17
29 / 100
 3183 ms 436964 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 <= 100000; 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 3078 ms 215572 KB Output is correct
2 Correct 3056 ms 215720 KB Output is correct
3 Correct 3054 ms 215800 KB Output is correct
4 Correct 3056 ms 215656 KB Output is correct
5 Correct 3051 ms 215616 KB Output is correct
6 Correct 3046 ms 215636 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3078 ms 215572 KB Output is correct
2 Correct 3056 ms 215720 KB Output is correct
3 Correct 3054 ms 215800 KB Output is correct
4 Correct 3056 ms 215656 KB Output is correct
5 Correct 3051 ms 215616 KB Output is correct
6 Correct 3046 ms 215636 KB Output is correct
7 Correct 3078 ms 215620 KB Output is correct
8 Correct 3055 ms 215540 KB Output is correct
9 Correct 3057 ms 215668 KB Output is correct
10 Correct 3039 ms 215564 KB Output is correct
11 Correct 3048 ms 215556 KB Output is correct
12 Correct 3058 ms 215536 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3078 ms 215572 KB Output is correct
2 Correct 3056 ms 215720 KB Output is correct
3 Correct 3054 ms 215800 KB Output is correct
4 Correct 3056 ms 215656 KB Output is correct
5 Correct 3051 ms 215616 KB Output is correct
6 Correct 3046 ms 215636 KB Output is correct
7 Correct 3078 ms 215620 KB Output is correct
8 Correct 3055 ms 215540 KB Output is correct
9 Correct 3057 ms 215668 KB Output is correct
10 Correct 3039 ms 215564 KB Output is correct
11 Correct 3048 ms 215556 KB Output is correct
12 Correct 3058 ms 215536 KB Output is correct
13 Runtime error 3183 ms 436964 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 3078 ms 215572 KB Output is correct
2 Correct 3056 ms 215720 KB Output is correct
3 Correct 3054 ms 215800 KB Output is correct
4 Correct 3056 ms 215656 KB Output is correct
5 Correct 3051 ms 215616 KB Output is correct
6 Correct 3046 ms 215636 KB Output is correct
7 Correct 3078 ms 215620 KB Output is correct
8 Correct 3055 ms 215540 KB Output is correct
9 Correct 3057 ms 215668 KB Output is correct
10 Correct 3039 ms 215564 KB Output is correct
11 Correct 3048 ms 215556 KB Output is correct
12 Correct 3058 ms 215536 KB Output is correct
13 Runtime error 3183 ms 436964 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 3078 ms 215572 KB Output is correct
2 Correct 3056 ms 215720 KB Output is correct
3 Correct 3054 ms 215800 KB Output is correct
4 Correct 3056 ms 215656 KB Output is correct
5 Correct 3051 ms 215616 KB Output is correct
6 Correct 3046 ms 215636 KB Output is correct
7 Correct 3078 ms 215620 KB Output is correct
8 Correct 3055 ms 215540 KB Output is correct
9 Correct 3057 ms 215668 KB Output is correct
10 Correct 3039 ms 215564 KB Output is correct
11 Correct 3048 ms 215556 KB Output is correct
12 Correct 3058 ms 215536 KB Output is correct
13 Runtime error 3183 ms 436964 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -