oj.uz

Submission #642936

# Submission time Handle Problem Language Result Execution time Memory
642936 2022-09-20T21:29:04 Z danikoynov Present (RMI21_present) C++14
29 / 100
 1119 ms 174508 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 int maxn = 1e6 + 10, maxnum = 150;
vector < vector < int > > st;
int gcd[maxnum][maxnum];
void preprocess()
{
    for (int i = 1; i < maxnum; i ++)
        for (int j = 1; j < maxnum; j ++)
            gcd[i][j] = __gcd(i, j);
    int mask = 0;
    while(st.size() < maxn)
    {
        vector < int > num;
        for (int bit = 0; (1 << bit) <= mask; bit ++)
            if ((mask & (1 << bit)))
                num.push_back(bit + 1);

        bool tf = true;
        int atl = 0;
        for (int i = 0; i < num.size() && tf; i ++)
            for (int j = i + 1; j < num.size(); j ++)
            {
                int 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()
{
    int n;
    cin >> n;
    cout << st[n].size();
    for (int v : st[n])
        cout << " " << v;
    cout << endl;

}

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

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 86276 KB Output is correct
2 Correct 1104 ms 86140 KB Output is correct
3 Correct 1050 ms 86124 KB Output is correct
4 Correct 1112 ms 86052 KB Output is correct
5 Correct 1040 ms 86120 KB Output is correct
6 Correct 1103 ms 86060 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 86276 KB Output is correct
2 Correct 1104 ms 86140 KB Output is correct
3 Correct 1050 ms 86124 KB Output is correct
4 Correct 1112 ms 86052 KB Output is correct
5 Correct 1040 ms 86120 KB Output is correct
6 Correct 1103 ms 86060 KB Output is correct
7 Correct 1084 ms 86076 KB Output is correct
8 Correct 1039 ms 86020 KB Output is correct
9 Correct 1113 ms 86176 KB Output is correct
10 Correct 1066 ms 86088 KB Output is correct
11 Correct 1063 ms 86028 KB Output is correct
12 Correct 1049 ms 86196 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 86276 KB Output is correct
2 Correct 1104 ms 86140 KB Output is correct
3 Correct 1050 ms 86124 KB Output is correct
4 Correct 1112 ms 86052 KB Output is correct
5 Correct 1040 ms 86120 KB Output is correct
6 Correct 1103 ms 86060 KB Output is correct
7 Correct 1084 ms 86076 KB Output is correct
8 Correct 1039 ms 86020 KB Output is correct
9 Correct 1113 ms 86176 KB Output is correct
10 Correct 1066 ms 86088 KB Output is correct
11 Correct 1063 ms 86028 KB Output is correct
12 Correct 1049 ms 86196 KB Output is correct
13 Runtime error 1119 ms 174508 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 1085 ms 86276 KB Output is correct
2 Correct 1104 ms 86140 KB Output is correct
3 Correct 1050 ms 86124 KB Output is correct
4 Correct 1112 ms 86052 KB Output is correct
5 Correct 1040 ms 86120 KB Output is correct
6 Correct 1103 ms 86060 KB Output is correct
7 Correct 1084 ms 86076 KB Output is correct
8 Correct 1039 ms 86020 KB Output is correct
9 Correct 1113 ms 86176 KB Output is correct
10 Correct 1066 ms 86088 KB Output is correct
11 Correct 1063 ms 86028 KB Output is correct
12 Correct 1049 ms 86196 KB Output is correct
13 Runtime error 1119 ms 174508 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 1085 ms 86276 KB Output is correct
2 Correct 1104 ms 86140 KB Output is correct
3 Correct 1050 ms 86124 KB Output is correct
4 Correct 1112 ms 86052 KB Output is correct
5 Correct 1040 ms 86120 KB Output is correct
6 Correct 1103 ms 86060 KB Output is correct
7 Correct 1084 ms 86076 KB Output is correct
8 Correct 1039 ms 86020 KB Output is correct
9 Correct 1113 ms 86176 KB Output is correct
10 Correct 1066 ms 86088 KB Output is correct
11 Correct 1063 ms 86028 KB Output is correct
12 Correct 1049 ms 86196 KB Output is correct
13 Runtime error 1119 ms 174508 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -