oj.uz

Submission #980314

# Submission time Handle Problem Language Result Execution time Memory
980314 2024-05-12T04:57:04 Z sleepntsheep Prisoner Challenge (IOI22_prison) C++17
10 / 100
 10 ms 1112 KB 
#include "prison.h"
//#include<cstdio>

#include <vector>

std::vector<std::vector<int>> devise_strategy(int N) {

    constexpr int B = 2, X = 26;
    std::vector<std::vector<int> > s(X+1, std::vector<int>(N+1));

    auto get = [&](int x, int i)
    {
        while(i--) x/=B;
        return x%B;
    };


    auto write = [&](int at,int j,int x) { s[at][j] = x; };
    write(0, 0, 0);
    for(int i=1;i<=N;++i)
    {
        int d=get(i, 13);
        write(0, i, 1+12*2+d);
    }

    for(int read=1;read<=X;++read)
    {
        auto write_ = [&](int j,int x) { write(read,j,x); };

        int at=(read-1)/B;
        int dd=(read-1)%B;
        int turn=((read-1)/2)%2 ? 'A':'B';

        if(turn=='B')
            write_(0, 1);
        else
            write_(0, 0);

        for(int i=1;i<=N;++i)
        {
            int ee=get(i,at);
            int ff=at>0?get(i,at-1):-1;

            if(ee==dd)
                write_(i, 1+(at-1)*2+ff);
            else
            {
                if(turn == 'B')
                    write_(i, ee>dd?-1:-2);
                else
                    write_(i, ee>dd?-2:-1);
            }
        }
    }


    return s;

    /*
    // * compare digits-by-digits
    // *
    // * On base B, this happens ln(N)/ln(B) iterations
    // * each iterations need B place to store the result,
    // * and another to denotes that one need to check the next bits
    // * f(B) = (B + 1) * ln(N) / ln (B) 

    constexpr int B = 3, X = 31;
    std::vector<std::vector<int> > s(X+1, std::vector<int>(N+1));

    auto get = [&](int x, int i)
    {
        while(i--) x/=B;
        return x%B;
    };

    for(int read=0;read<=X;++read)
    {
        auto write = [&](int j,int x) { s[read][j] = x; };

        int at=(read)/(B+1);
        int dd=(read)%(B+1);
        if(dd>0)
        {
            write(0, 1);
            --dd;
            for(int i=1;i<=N;++i)
            {
                int ee=get(i,at);
                if(ee==dd)
                    write(i, (at)*(B+1));
                else
                    write(i, ee>dd?-1:-2);
            }
        }
        else
        {
            write(0,0);
            for(int i=1;i<=N;++i)
            {
                int to = at ? at - 1 : 7;
                write(i, to*(B+1)+1+get(i,to));
            }
        }
    }

    return s;

    */
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Partially correct 1 ms 348 KB Output is partially correct
3 Partially correct 0 ms 348 KB Output is partially correct
4 Partially correct 5 ms 604 KB Output is partially correct
5 Incorrect 10 ms 1112 KB Strategy failed for N=4096, A=4096, B=4090
6 Halted 0 ms 0 KB -