oj.uz

Submission #828560

# Submission time Handle Problem Language Result Execution time Memory
828560 2023-08-17T11:09:59 Z Amylopectin Prisoner Challenge (IOI22_prison) C++17
100 / 100
 9 ms 1424 KB 
#include "prison.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mxn = 1e5 + 10;
int thr[mxn] = {};
vector<int> fa;
vector<vector<int> > ans;
std::vector<std::vector<int>> devise_strategy(int n) 
{
  int i,j,cn,cm,fn,fm,cou = 7;
  thr[0] = 1;
  thr[1] = 4;
  thr[2] = 10;
  thr[3] = 22;
  for(i=4; i<10; i++)
  {
    thr[i] = (thr[i-1] * 3);
  }
  cou = 7;
  fa.push_back(0);
  for(i=1; i<=n; i++)
  {
    fa.push_back(1+(i/thr[cou]));
  }
  ans.push_back(fa);
  cou = 8;
  for(i=1; i<16; i++)
  {
    fa.clear();
    if(i%3 == 1)
    {
      cou --;
    }
    cm = (i-1) % 3;
    if(((i-1)/3) % 2 == 0)
    {
      fa.push_back(1);
      for(j=1; j<=n; j++)
      {
        cn = (j % thr[cou+1]) / thr[cou];
        if(cn < cm)
        {
          fa.push_back(-2);
        }
        else if(cn > cm)
        {
          fa.push_back(-1);
        }
        else 
        {
          if(i>=13)
          {
            fn = j % 22;
            if(fn == 0)
            {
              fa.push_back(-2);
            }
            else if(fn == 21)
            {
              fa.push_back(-1);
            }
            else 
            {
              fa.push_back(16+((fn-1)/10));
            }
          }
          else 
          {
            fn = (j % thr[cou]) / thr[cou-1];
            fa.push_back(i-cm + 3 + fn);
          }
        }
      }
    }
    else 
    {
      fa.push_back(0);
      // if(i>15)
      // {
      //   for(j=1; j<=n; j++)
      //   {
      //     cn = (j % thr[cou+1]) / thr[cou];
      //     if(cn < cm)
      //     {
      //       fa.push_back(-1);
      //     }
      //     else if(cn > cm)
      //     {
      //       fa.push_back(-2);
      //     }
      //     else 
      //     {
      //       fn = (j % thr[cou]) / 4;
      //       fa.push_back(i-cm + 3 + fn);
      //     }
      //   }
      // }
      // else 
      {
        for(j=1; j<=n; j++)
        {
          cn = (j % thr[cou+1]) / thr[cou];
          if(cn < cm)
          {
            fa.push_back(-1);
          }
          else if(cn > cm)
          {
            fa.push_back(-2);
          }
          else 
          {
            fn = (j % thr[cou]) / thr[cou-1];
            fa.push_back(i-cm + 3 + fn);
          }
        }
      }
      
    }
    ans.push_back(fa);
  }
  for(i=0; i<2; i++)
  {
    fa.clear();
    fa.push_back(0);
    cm = i;
    for(j=1; j<=n; j++)
      {
        cn = (j % 22);
        if(cn == 0)
        {
          fa.push_back(-1);
        }
        else if(cn == 21)
        {
          fa.push_back(-2);
        }
        else 
        {
          cn = (cn-1) / 10;
          if(cn < cm)
          {
            fa.push_back(-1);
          }
          else if(cn > cm)
          {
            fa.push_back(-2);
          }
          else 
          {
            fn = ((j%22) - 1) % 10;
            // fn = (j % thr[1]) / thr[0];
            if(fn == 0)
            {
              fa.push_back(-1);
            }
            else if(fn == 9)
            {
              fa.push_back(-2);
            }
            else 
            {
              fa.push_back(18 + ((fn-1) / 4));
            }
          }
        }
      }
      ans.push_back(fa);
  }
  for(i=0; i<2; i++)
  {
    fa.clear();
    fa.push_back(1);
    cm = i;
    for(j=1; j<=n; j++)
      {
        cn = (j % 22);
        if(cn == 0 || cn == 1 || cn == 11)
        {
          fa.push_back(-2);
        }
        else if(cn == 21 || cn == 10 || cn == 20)
        {
          fa.push_back(-1);
        }
        else 
        {
          cn = (((cn-1) % 10)-1) / 4;
          if(cn < cm)
          {
            fa.push_back(-2);
          }
          else if(cn > cm)
          {
            fa.push_back(-1);
          }
          else 
          {
            fn = ((((j%22) - 1) % 10)-1) % 4;
            // fn = (j % thr[1]) / thr[0];
            if(fn == 0)
            {
              fa.push_back(-2);
            }
            else if(fn == 3)
            {
              fa.push_back(-1);
            }
            else 
            {
              fa.push_back(20);
            }
          }
        }
      }
      ans.push_back(fa);
  }
  fa.clear();
  fa.push_back(0);
  for(j=1; j<=n; j++)
  {
    if(((((j%22) - 1) % 10)-1) % 4 <= 1)
    {
      fa.push_back(-1);
    }
    else 
    {
      fa.push_back(-2);
    }
  }
  ans.push_back(fa);
  return {ans};
}

Compilation message

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:13:20: warning: unused variable 'fm' [-Wunused-variable]
   13 |   int i,j,cn,cm,fn,fm,cou = 7;
      |                    ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 7 ms 1196 KB Output is correct
6 Correct 9 ms 1424 KB Output is correct
7 Correct 9 ms 1356 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 7 ms 1136 KB Output is correct