oj.uz

Submission #691831

# Submission time Handle Problem Language Result Execution time Memory
691831 2023-01-31T16:57:21 Z PoonYaPat Prisoner Challenge (IOI22_prison) C++17
100 / 100
 14 ms 1876 KB 
#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> v[5001];
int s[5001][5001];
vector<int> a={3,3,3,3,3,2,2,1};

void trans(int x, int l, int r, int cnt) {
    if (x==l) v[x].push_back(-1);
    else if (x==r) v[x].push_back(-2);
    else {
        int par=(r-l-1)/a[cnt];
        if (x<=l+par) {
            v[x].push_back(1);
            trans(x,l+1,l+par,cnt+1);
        } else if (x<=l+2*par) {
            v[x].push_back(2);
            trans(x,l+par+1,l+2*par,cnt+1);
        } else {
            v[x].push_back(3);
            trans(x,l+2*par+1,r-1,cnt+1);
        }
    }
}

vector<vector<int>> devise_strategy(int n) {
    for (int i=1; i<=n; ++i) trans(i,1,5588,0);

    s[0][0]=1; //look at B
    for (int i=1; i<=n; ++i) {
        if (v[i][0]==-1) s[0][i]=-2;
        else if (v[i][0]==-2) s[0][i]=-1;
        else s[0][i]=v[i][0];
    }

    int idx=0;
    for (int k=0; k<a.size(); ++k) {
        for (int i=idx+1; i<=idx+a[k]; ++i) {

            s[i][0]=k%2;

            //read i -> range i-idx
            for (int j=1; j<=n; ++j) {
                //open bag then see j

                if (v[j].size()<k+1) s[i][j]=0;
                else if (v[j][k]==-1 || (v[j][k]<i-idx && v[j][k]>0)) {
                    if (k%2==0) s[i][j]=-1;
                    else s[i][j]=-2;

                } else if (v[j][k]==-2 || (v[j][k]>i-idx && v[j][k]>0)) {

                    if (k%2==0) s[i][j]=-2;
                    else s[i][j]=-1;

                } else { //v[j][k]==i-idx

                    if (v[j][k+1]==-1) {
                        if (k%2==0) s[i][j]=-1;
                        else s[i][j]=-2;

                    } else if (v[j][k+1]==-2) {
                        if (k%2==0) s[i][j]=-2;
                        else s[i][j]=-1;

                    } else s[i][j]=v[j][k+1]+idx+a[k];

                }
            }

        }
        idx+=a[k];
    }

    vector<vector<int>> ans;
    for (int i=0; i<=20; ++i) {
        vector<int> temp;
        for (int j=0; j<=n; ++j) temp.push_back(s[i][j]);
        ans.push_back(temp);
    }
    return ans;
}

Compilation message

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int k=0; k<a.size(); ++k) {
      |                   ~^~~~~~~~~
prison.cpp:47:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |                 if (v[j].size()<k+1) s[i][j]=0;
      |                     ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 552 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 424 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 3 ms 556 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 1 ms 420 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 10 ms 1656 KB Output is correct
6 Correct 14 ms 1856 KB Output is correct
7 Correct 11 ms 1876 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 548 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 8 ms 1064 KB Output is correct
12 Correct 9 ms 1632 KB Output is correct