oj.uz

Submission #631191

# Submission time Handle Problem Language Result Execution time Memory
631191 2022-08-17T19:02:10 Z TimDee Prisoner Challenge (IOI22_prison) C++17
100 / 100
 10 ms 1364 KB 
#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

int A = 0;
int B = 1;
int n;

vector<vector<int>> a(21,vector<int>(5001,0));

void fill(int ind, int l, int r, int type) {

  //if (ind!=0) return;
  //if (1295-type>=l && 1295-type<=r) cout<<"Fill "<<ind<<' '<<l<<' '<<r<<' '<<type<<'\n';
  //int x; cin>>x;

  if (r-l+1==6) {

    a[ind][0]=type;
    
    a[ind][l]=-1;
    a[ind][r]=-2;
    a[ind][l+1]=a[ind][l+2]=19;
    a[ind][l+3]=a[ind][l+4]=20;

    a[19][l+1]=a[19][l]=-2; a[19][l+2]=a[19][l+3]=a[19][l+4]=a[19][r]=-1;
    a[20][l]=a[20][l+1]=a[20][l+2]=a[20][l+3]=a[20][l]=-2; a[20][l+4]=a[20][r]=-1;
    a[19][0]=a[20][0]=1;

    return;

  }

  if (r-l+1==5) {

    a[ind][0]=type;
    
    a[ind][l]=-1;
    a[ind][r]=-2;
    a[ind][l+1]=a[ind][l+2]=19;
    a[ind][l+3]=20;

    a[19][l+1]=a[19][l]=-2; a[19][l+2]=a[19][l+3]=a[19][r]=-1;
    a[20][l]=a[20][l+1]=a[20][l+2]=a[20][l]=-2; a[20][r]=-1;
    a[19][0]=a[20][0]=1;

    return;

  }

  if (r-l+1==4) {

    a[ind][0]=type;
    
    a[ind][l]=-1;
    a[ind][r]=-2;
    a[ind][l+1]=19;
    a[ind][l+2]=20;

    a[19][l]=-2; a[19][l+2]=a[19][r]=-1;
    a[20][l]=a[20][l+1]=-2; a[20][r]=-1;
    a[19][0]=a[20][0]=1;

    return;

  }

  a[ind][0]=type;
  a[ind][l]=-(type+1);
  a[((ind+2)/3+1)*3-2][l]=-((type^1)+1);
  a[((ind+2)/3+1)*3-1][l]=-((type^1)+1);
  a[((ind+2)/3+1)*3][l]=-((type^1)+1);

  a[ind][r]=-((type^1)+1);
  a[((ind+2)/3+1)*3-2][r]=-(type+1);
  a[((ind+2)/3+1)*3-1][r]=-(type+1);
  a[((ind+2)/3+1)*3][r]=-(type+1);

  int sz = (r-l+1)/3;

  for (int i=l+1; i<min(l+1+sz,n+1); ++i) a[ind][i]=((ind+2)/3+1)*3-2;
  for (int i=l+1+sz; i<min(r,n+1); ++i) a[((ind+2)/3+1)*3-2][i]=-(type+1);
  fill(((ind+2)/3+1)*3-2,l+1,l+1+sz-1,type^1);
  
  for (int i=l+1+sz; i<min(l+1+2*sz,n+1); ++i) a[ind][i]=((ind+2)/3+1)*3-1;
  for (int i=l+1; i<min(l+1+sz,n+1); ++i) a[((ind+2)/3+1)*3-1][i]=-((type^1)+1);
  for (int i=l+1+2*sz; i<min(r,n+1); ++i) a[((ind+2)/3+1)*3-1][i]=-(type+1);
  fill(((ind+2)/3+1)*3-1,l+1+sz,l+1+2*sz-1,type^1);
  
  for (int i=l+1+2*sz; i<min(r,n+1); ++i) a[ind][i]=((ind+2)/3+1)*3;
  for (int i=l+1; i<min(l+1+2*sz,n+1); ++i) a[((ind+2)/3+1)*3][i]=-((type^1)+1);
  fill(((ind+2)/3+1)*3,l+1+2*sz,r-1,type^1);

}

vector<vector<int>> devise_strategy(int _n) {
  
  n=_n;
  int sz=5000;
  a.assign(21,vector<int>(n+1,0));

  fill(0,1,5000,A);

  for (auto x:a) {
    //for (auto y:x) cout<<y<<' '; cout<<'\n';
  }
  
  return a;

}

Compilation message

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:99:7: warning: unused variable 'sz' [-Wunused-variable]
   99 |   int sz=5000;
      |       ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 5 ms 980 KB Output is correct
5 Correct 8 ms 1284 KB Output is correct
6 Correct 10 ms 1364 KB Output is correct
7 Correct 10 ms 1364 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 5 ms 1000 KB Output is correct
12 Correct 8 ms 1200 KB Output is correct