oj.uz

Submission #856460

# Submission time Handle Problem Language Result Execution time Memory
856460 2023-10-03T14:53:40 Z Tenis0206 Present (RMI21_present) C++11
70 / 100
 2574 ms 428 KB 
#include <bits/stdc++.h>

using namespace std;

const int vmax = 40;
const int bsize = 1e6;

long long prec[] = {0, 16875560, 37996352, 58218880, 85307432, 115369928, 145427604, 177042784, 216122416, 265554224, 284435344, 306146560, 325960320, 352927552, 382573344, 413083264, 444714560, 482943904, 531634464, 572835264, 616833168, 678626048, 752552064, 822161544, 863457024, 921961104, 986877184, 1075004936, 1092852544, 1113627204, 1136479008, 1162610400, 1193154120, 1223833104, 1256156288, 1295885856, 1343045008, 1360744608, 1381436744, 1403603744, 1430406184, 1460534048, 1491402948, 1523149600, 1562765088, 1611914256, 1649817352, 1698972808, 1761883268, 1842813056, 1901206024, 1946481864, 2003981832, 2070011456, 2150901380, 2176517440, 2201334812, 2234282848, 2271519196, 2311617632, 2351858884, 2406329440, 2435126212, 2459301416, 2489588784, 2525896784, 2565646932, 2604318880, 2655911956, 2708542760, 2765833280, 2843599008, 2952561920, 2997065292, 3065024792, 3146055748, 3227129936, 3255846960, 3278828640, 3313567032, 3355677268, 3391663764, 3432175632, 3490534720, 3512710304, 3540038892, 3569993312, 3608216104, 3645338720, 3685690176, 3739951184, 3793916184, 3855889672, 3931023696, 4030969484, 4081131816, 4153262400, 4237406480, 4309729472, 4342780672, 4380394592, 4425291040, 4474011712, 4535825536, 4580588672, 4614042976, 4651819312, 4697763872, 4746252416, 4807990400, 4872026368, 4947542592, 5057145088, 5140582720, 5216670528, 5326559232, 5387725440, 5421277664, 5459721088, 5504816128, 5555339520, 5618559296, 5658462976, 5692072992, 5731341184, 5775854976, 5826908288, 5891321920, 5954478208, 6034753664, 6147848448, 6223425808, 6304068224, 6416707712, 6476249216, 6516167488, 6572782880, 6632674432, 6711830784, 6749723200, 6796613248, 6850822272, 6917049600, 6996516992, 7085105280, 7218689664, 7315146880, 7421137024, 7528903712, 7570981280, 7621435680, 7682351616, 7752447360, 7805967392, 7852021088, 7902097984, 7959785600, 8036845696, 8120382528, 8226312448, 8355116864, 8442466880, 8588429312, 8607801864, 8629292576, 8651627072, 8680212160, 8711099968, 8743205008, 8775806992, 8819774976, 8861488720, 8881514568, 8902246944, 8927631936, 8959296776, 8988944960, 9020668480, 9053292800, 9099084320, 9142144208, 9183942464, 9242916928, 9307697296, 9397735248, 9436216064, 9489765440, 9552097408, 9634335808, 9675461648, 9699525080, 9718682016, 9745990816, 9776563264, 9807360288, 9840232592, 9880027968, 9930896704, 9949810048, 9971340560, 9993530912, 10022304160, 10053041200, 10085283712, 10117752064, 10161543744, 10206271680, 10246819264, 10303646544, 10368805504, 10450380096, 10503562560, 10545595792, 10609496272, 10679453760, 10744643088, 10774052480, 10801398560, 10839528528, 10876116128, 10912932128, 10962735300, 11010688832, 11040105104, 11062939848, 11100281408, 11140829840, 11178062480, 11224006976, 11278892864, 11329204744, 11403609664, 11487524096, 11568597248, 11626710176, 11706434304, 11811366632, 11833844352, 11861541792, 11893231952, 11931407936, 11969517184, 12013288608, 12067877760, 12098830640, 12123894336, 12154097744, 12193700128, 12233040068, 12271432416, 12327536128, 12382933456, 12440366336, 12520071248, 12619992128, 12669348480, 12740481696, 12824422720, 12900705168, 12935431504, 12975151376, 13021336384, 13073922464, 13140308608, 13179646240, 13214636096, 13258270880, 13304598640, 13360211232, 13427303824, 13494250240, 13587761408, 13697159504, 13764661968, 13859000640, 13963310032, 13997338240, 14034018464, 14077726016, 14130652864, 14193654592, 14240941072, 14275453584, 14315642912, 14361994400, 14413354624, 14479238176, 14543101456, 14623900224, 14737322144, 14814472832, 14898196560, 15010984192, 15067613344, 15112391712, 15169563040, 15235981984, 15306397264, 15351175488, 15403027520, 15460507936, 15536232608, 15611412752, 15711019648, 15845734528, 15938704592, 16061328640, 16137007376, 16179019040, 16237026880, 16299279616, 16377174656, 16417065248, 16469254432, 16526725760, 16597228352, 16679150224, 16774464576, 16913805648, 16996670080, 17117079872, 17201135780, 17239426336, 17291231240, 17353729056, 17437326368, 17481255168, 17520334440, 17574418184, 17639686944, 17727658816, 17817693952, 17966785664, 18055828488, 18183320704, 18275091784, 18313969952, 18365674016, 18427977764, 18511959172, 18555679924, 18594512272, 18649014408, 18714050848, 18803080960, 18892461448, 19043190280, 19130564866, 19259368704, 19355342404, 19408459010, 19480343840, 19571790368, 19631948872, 19686109700, 19762034212, 19859804704, 19969118280, 20143815680, 20260051456, 20411450624, 20458927752, 20525201696, 20607169824, 20688650312, 20738599200, 20806829316, 20892406786, 20994659876, 21152320000, 21282665472, 21462073632, 21529663016, 21604176648, 21712998920, 21786331176, 21858110752, 21958867488, 22084147202, 22284697672, 22424462464, 22574601888, 22641135882, 22732483200, 22834112008, 22897066088, 22983246368, 23102687112, 23253288456, 23425336840, 23623542408, 23699968584, 23810584864, 23925016896, 24012477000, 24144834848, 24325820672, 24533308576, 24722030688, 24809800200, 24936686608, 25025193216, 25128966944, 25272799816, 25503780936, 25692225824, 25798117536, 25839332128, 25894290948, 25960935428, 26043036416, 26081607944, 26129453216, 26190442656, 26265852192, 26351210564, 26462064000, 26600483852, 26698138760, 26846499688, 26884229792, 26931728772, 26990681220, 27065308704, 27130951840, 27169183424, 27222868256, 27286470820, 27372392992, 27454675264, 27586270728, 27702420104, 27819697280, 27937039364, 27987906856, 28058169988, 28152817952, 28219744932, 28273854024, 28348736768, 28448444960, 28558240384, 28733081092, 28848491072, 29002012740, 29050811656, 29121139784, 29207301136, 29282878668, 29334651424, 29410670464, 29502527776, 29611093248, 29788005632, 29901384832, 30070975104, 30136417424, 30221639968, 30337652552, 30401645864, 30485868832, 30606244872, 30750434432, 30930379904, 31128354976, 31197039392, 31277636224, 31395141152, 31462399296, 31542285456, 31658086688, 31793130112, 31982841600, 32154788992, 32270674560, 32380384544, 32502449056, 32590209544, 32721365280, 32893134080, 33107841864, 33308031264, 33396214304, 33527237008, 33620480576, 33727186720, 33877627016, 34108444744, 34311653504, 34381899528, 34414927296, 34479441108, 34528270036, 34582375472, 34641675924, 34673124448, 34729663024, 34781979232, 34828513568, 34914552128, 35033099972, 35170096324, 35271350344, 35418948160, 35458484384, 35491431496, 35559249056, 35604313828, 35669142080, 35719537824, 35752469920, 35807586464, 35859370148, 35907936900, 35996000448, 36112605456, 36250058820, 36363502656, 36508114468, 36545178628, 36608836612, 36665179968, 36725808704, 36793897376, 36832949316, 36913260432, 36959524624, 37047141444, 37184705732, 37335641920, 37482497936, 37597583184, 37636359072, 37717413060, 37757740832, 37849471204, 37885982084, 37941270176, 38005463712, 38058075792, 38161339408, 38309940864, 38460492944, 38633813520, 38695996168, 38784995912};

int my_gcd[vmax + 5][vmax + 5];

long long get_val_gcd(long long val)
{
    int k = 0;
    for(int b=0;b<=vmax;b++)
    {
        if((val & (1LL<<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<<(my_gcd[a][b] - 1));
        }
    }
    return val;
}

long long get_next(long long val)
{
    long long 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 start = (k / bsize) * bsize;
    long long rez = prec[k / bsize];
    for(int i=start+1;i<=k;i++)
    {
        rez = get_next(rez);
    }
    long long 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';
}

int main()
{
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    for(int i=1; i<=vmax; i++)
    {
        for(int j=1; j<=vmax; j++)
        {
            my_gcd[i][j] = __gcd(i,j);
        }
    }
    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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1109 ms 420 KB Output is correct
8 Correct 1668 ms 424 KB Output is correct
9 Correct 1277 ms 348 KB Output is correct
10 Correct 1512 ms 416 KB Output is correct
11 Correct 747 ms 344 KB Output is correct
12 Correct 1442 ms 416 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1109 ms 420 KB Output is correct
8 Correct 1668 ms 424 KB Output is correct
9 Correct 1277 ms 348 KB Output is correct
10 Correct 1512 ms 416 KB Output is correct
11 Correct 747 ms 344 KB Output is correct
12 Correct 1442 ms 416 KB Output is correct
13 Correct 1909 ms 348 KB Output is correct
14 Correct 1723 ms 420 KB Output is correct
15 Correct 2486 ms 344 KB Output is correct
16 Correct 1853 ms 428 KB Output is correct
17 Correct 2270 ms 424 KB Output is correct
18 Correct 2574 ms 420 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1109 ms 420 KB Output is correct
8 Correct 1668 ms 424 KB Output is correct
9 Correct 1277 ms 348 KB Output is correct
10 Correct 1512 ms 416 KB Output is correct
11 Correct 747 ms 344 KB Output is correct
12 Correct 1442 ms 416 KB Output is correct
13 Correct 1909 ms 348 KB Output is correct
14 Correct 1723 ms 420 KB Output is correct
15 Correct 2486 ms 344 KB Output is correct
16 Correct 1853 ms 428 KB Output is correct
17 Correct 2270 ms 424 KB Output is correct
18 Correct 2574 ms 420 KB Output is correct
19 Incorrect 2390 ms 420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1109 ms 420 KB Output is correct
8 Correct 1668 ms 424 KB Output is correct
9 Correct 1277 ms 348 KB Output is correct
10 Correct 1512 ms 416 KB Output is correct
11 Correct 747 ms 344 KB Output is correct
12 Correct 1442 ms 416 KB Output is correct
13 Correct 1909 ms 348 KB Output is correct
14 Correct 1723 ms 420 KB Output is correct
15 Correct 2486 ms 344 KB Output is correct
16 Correct 1853 ms 428 KB Output is correct
17 Correct 2270 ms 424 KB Output is correct
18 Correct 2574 ms 420 KB Output is correct
19 Incorrect 2390 ms 420 KB Output isn't correct
20 Halted 0 ms 0 KB -