oj.uz

Submission #856426

# Submission time Handle Problem Language Result Execution time Memory
856426 2023-10-03T13:13:36 Z Tenis0206 Present (RMI21_present) C++11
8 / 100
 4000 ms 452 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int vmax = 40;

int get_val_gcd(int val)
{
    int k = 0;
    for(int b=0;b<=vmax;b++)
    {
        if((val & (1<<b)) != 0)
        {
            k = b + 1;
        }
    }
    for(int a=k;a>=1;a--)
    {
        for(int b=a-1;b>=1;b--)
        {
            if(!(val & (1LL<<(a - 1))) || !(val & (1LL<<(b - 1))) )
            {
                continue;
            }
            val |= (1LL<<(__gcd(a,b) - 1));
        }
    }
    return val;
}

int get_next(int val)
{
    int val_gcd = get_val_gcd(val);
    for(int b=1;b<=vmax;b++)
    {
        if((val & (1LL<<(b-1))) == 0 && (val_gcd & (1LL<<(b-1))) == 0)
        {
            val += (1LL<<(b - 1));
            break;
        }
        if((val & (1LL<<(b-1))) != 0)
        {
            val -= (1LL<<(b - 1));
        }
    }
    return val;
}

void solve_test()
{
    int k;
    cin>>k;
    int rez = 0;
    for(int i=1;i<=k;i++)
    {
        rez = get_next(rez);
    }
    int val_gcd = get_val_gcd(rez);
    vector<int> r;
    for(int val=1;val<=vmax;val++)
    {
        if(val_gcd & (1LL<<(val-1)))
        {
            r.push_back(val);
        }
    }
    cout<<r.size()<<' ';
    for(auto it : r)
    {
        cout<<it<<' ';
    }
    cout<<'\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    int t;
    cin>>t;
    for(int test=1;test<=t;test++)
    {
        solve_test();
    }
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3012 ms 444 KB Output is correct
8 Execution timed out 4042 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3012 ms 444 KB Output is correct
8 Execution timed out 4042 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3012 ms 444 KB Output is correct
8 Execution timed out 4042 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3012 ms 444 KB Output is correct
8 Execution timed out 4042 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -