oj.uz

Submission #596523

# Submission time Handle Problem Language Result Execution time Memory
596523 2022-07-14T19:51:29 Z ThegeekKnight16 Brperm (RMI20_brperm) C++14
0 / 100
 3000 ms 4720 KB 
#include <bits/stdc++.h>
#include <brperm.h>
using namespace std;
const int MAXN = 5e5 + 10;
int Roupas[MAXN], pos[MAXN];

int findK(int num)
{
    for (int k = 20; k >= 0; k--) if (num & (1 << k)) return k;
}

int inv(int num, int K)
{
    int resp = 0;
    for (int k = K; k >= 0; k--) resp += (num & (1 << k)) ? (1 << (K - k)) : 0;
    return resp;
}

int query(int X, int K)
{
    int Y = X + (1 << K) - 1;
    
    int maxK = findK(Y);
    
    for (int i = X; i <= Y; i++) pos[i] = inv(i - X, maxK);
    
    for (int i = X; i <= Y; i++) if (Roupas[i] != Roupas[pos[i]] || pos[i] < X || pos[i] > Y) {cerr << i << "!=" << pos[i]; return 0;}
    return 1;
}

void init(int N, const char s[])
{
    for (int i = 0; i < N; i++) Roupas[i] = s[i];
    int K = findK(N-1);
    for (int i = 0; i < N; i++) pos[i] = inv(i, K);
}

/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    init(8, "axxyxxyb");
    cout << query(0, 2);
}*/

Compilation message

brperm.cpp: In function 'int findK(int)':
brperm.cpp:10:1: warning: control reaches end of non-void function [-Wreturn-type]
   10 | }
      | ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1313 ms 2380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1313 ms 2380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 4720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1313 ms 2380 KB Output isn't correct
2 Halted 0 ms 0 KB -