oj.uz

Submission #642937

# Submission time Handle Problem Language Result Execution time Memory
642937 2022-09-20T21:30:21 Z danikoynov Present (RMI21_present) C++14
29 / 100
 1176 ms 269080 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll maxn = 1e6 + 10, maxnum = 150;
vector < vector < ll > > st;
ll gcd[maxnum][maxnum];
void preprocess()
{
    for (ll i = 1; i < maxnum; i ++)
        for (ll j = 1; j < maxnum; j ++)
            gcd[i][j] = __gcd(i, j);
    ll mask = 0;
    while(st.size() < maxn)
    {
        vector < ll > num;
        for (ll bit = 0; (1 << bit) <= mask; bit ++)
            if ((mask & (1 << bit)))
                num.push_back(bit + 1);

        bool tf = true;
        ll atl = 0;
        for (ll i = 0; i < num.size() && tf; i ++)
            for (ll j = i + 1; j < num.size(); j ++)
            {
                ll x = gcd[num[i]][num[j]];
                if ((mask & (1 << (x - 1))) == 0)
                {
                    atl = x;
                    tf = false;
                    break;
                }
            }

        if (tf)
        {
            st.push_back(num);
            mask ++;
        }
        else
            mask = (mask | (1 << (atl - 1)));

    }
    ///cout << "Done " << mask << endl;
    //exit(0);
}

void solve()
{
    ll n;
    cin >> n;
    cout << st[n].size();
    for (ll v : st[n])
        cout << " " << v;
    cout << endl;

}

int main()
{
    preprocess();
    ll t;
    cin >> t;
    while(t --)
        solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void preprocess()':
Main.cpp:40:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (ll i = 0; i < num.size() && tf; i ++)
      |                        ~~^~~~~~~~~~~~
Main.cpp:41:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for (ll j = i + 1; j < num.size(); j ++)
      |                                ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 132836 KB Output is correct
2 Correct 1098 ms 132852 KB Output is correct
3 Correct 1108 ms 132864 KB Output is correct
4 Correct 1114 ms 132884 KB Output is correct
5 Correct 1094 ms 132740 KB Output is correct
6 Correct 1087 ms 132724 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 132836 KB Output is correct
2 Correct 1098 ms 132852 KB Output is correct
3 Correct 1108 ms 132864 KB Output is correct
4 Correct 1114 ms 132884 KB Output is correct
5 Correct 1094 ms 132740 KB Output is correct
6 Correct 1087 ms 132724 KB Output is correct
7 Correct 1088 ms 132892 KB Output is correct
8 Correct 1092 ms 132688 KB Output is correct
9 Correct 1122 ms 132804 KB Output is correct
10 Correct 1150 ms 132852 KB Output is correct
11 Correct 1093 ms 132900 KB Output is correct
12 Correct 1094 ms 132780 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 132836 KB Output is correct
2 Correct 1098 ms 132852 KB Output is correct
3 Correct 1108 ms 132864 KB Output is correct
4 Correct 1114 ms 132884 KB Output is correct
5 Correct 1094 ms 132740 KB Output is correct
6 Correct 1087 ms 132724 KB Output is correct
7 Correct 1088 ms 132892 KB Output is correct
8 Correct 1092 ms 132688 KB Output is correct
9 Correct 1122 ms 132804 KB Output is correct
10 Correct 1150 ms 132852 KB Output is correct
11 Correct 1093 ms 132900 KB Output is correct
12 Correct 1094 ms 132780 KB Output is correct
13 Runtime error 1176 ms 269080 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 1091 ms 132836 KB Output is correct
2 Correct 1098 ms 132852 KB Output is correct
3 Correct 1108 ms 132864 KB Output is correct
4 Correct 1114 ms 132884 KB Output is correct
5 Correct 1094 ms 132740 KB Output is correct
6 Correct 1087 ms 132724 KB Output is correct
7 Correct 1088 ms 132892 KB Output is correct
8 Correct 1092 ms 132688 KB Output is correct
9 Correct 1122 ms 132804 KB Output is correct
10 Correct 1150 ms 132852 KB Output is correct
11 Correct 1093 ms 132900 KB Output is correct
12 Correct 1094 ms 132780 KB Output is correct
13 Runtime error 1176 ms 269080 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 1091 ms 132836 KB Output is correct
2 Correct 1098 ms 132852 KB Output is correct
3 Correct 1108 ms 132864 KB Output is correct
4 Correct 1114 ms 132884 KB Output is correct
5 Correct 1094 ms 132740 KB Output is correct
6 Correct 1087 ms 132724 KB Output is correct
7 Correct 1088 ms 132892 KB Output is correct
8 Correct 1092 ms 132688 KB Output is correct
9 Correct 1122 ms 132804 KB Output is correct
10 Correct 1150 ms 132852 KB Output is correct
11 Correct 1093 ms 132900 KB Output is correct
12 Correct 1094 ms 132780 KB Output is correct
13 Runtime error 1176 ms 269080 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -