oj.uz

Submission #674320

# Submission time Handle Problem Language Result Execution time Memory
674320 2022-12-23T17:10:54 Z Hostek Rack (eJOI19_rack) C++17
100 / 100
 4 ms 244 KB 
// https://oj.uz/problem/view/eJOI19_rack

// European Junior Olympiad in Informatics 2019
// Day 1 Tasks

// Hanging Rack

#include <bitset>
#include <iostream>

constexpr int mod = 1000 * 1000 * 1000 + 7;

long long pot(long long a, long long b) {
    if (b == 1) return a % mod;
    if (a == 0) return 0;
    if (b == 0) return 1;
    if (b % 2 == 1)
        return (a * pot(a, b - 1)) % mod;
    else {
        long long c = pot(a, b / 2);
        return (c * c) % mod;
    }
}

std::bitset<10000000> tab;

size_t convert_to_bin(long long n) {
    if (n == 0) {
        return 0;
    }

    long long i = 0;
    while (n > 0) {
        tab[i] = n % 2;

        n = n / 2;
        i++;
    }

    return i - 1;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    long long n, k;
    std::cin >> n >> k;

    k--;

    convert_to_bin(k);

    long long rack = 1;

    for (int i = 0; i < n; i++) {
        long long temp = tab[i] ? (pot(2, n - i - 1)) : tab[i];

        rack += temp;
        rack %= mod;
        // std::cout << tab[i] << " | val: " << temp << '\n';
    }
    // std::cout << '\n';

    std::cout << rack << '\n';

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 244 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 244 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 244 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 4 ms 212 KB Output is correct