제출 #677405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677405		Cross_Ratio	기억 압축 (JOI15_memory)	C++14	100 / 100	3812 ms	284128 KiB

memory

#include "Memory_lib.h"
#include <bits/stdc++.h>
using namespace std;
int pw[25];
int val(int s, int e, int M) {
    int val = 0, cnt = 1;
    for(int i=s;i<e;i++) {
        val += (M & pw[i])/pw[i] * cnt;
        cnt *= 2;
    }
    return val;
}
/*string s;
char Get(int v) {
    cout << v << ' ';
    assert(1<=v&&v<=s.length());
    return s[v-1];
}*/
//char Get(int);
int Memory(int N, int M) {
    int i;
    pw[0] = 1;
    for(i=1;i<=24;i++) pw[i] = pw[i-1] * 2;
    int st = val(0, 7, M);
    int pt = val(7, 14, M);
    int cnt = val(14, 21, M);
    int k = val(21, 22, M);
    if(st>=N) return -1;
    if(pt>=N) return -2;
    if(cnt>=N) return -2;
    //cout << st << ' ' << pt << ' ' << cnt << ' ' << k << '\n';
    if(st==pt) {
        //assert(1<=st+1&&st+1<=N);
        //assert(cnt==0);
        if(cnt!=0) return -2;
        if(st+1>N) return -2;
        char c = Get(st+1);
        if(c=='<' || c=='[') {
            if(st+1>=N) return -2;
            int v = st + pw[7] * (st+1) + pw[14] * 1 + pw[21] * (c=='<'?1:0);
            return v;
        }
        else {
            if(st-1<0) return -2;
            int v = st + pw[7] * (st - 1) + pw[14] * 1 + pw[21] * (c=='>'?1:0);
            return v;
        }
    }
    if(cnt<=0) return -2;
    //assert(cnt>=1);
    if(pt+1>N) return -2;
    char c = Get(pt+1);
    //assert(pt+1<=N);
    if(c=='<'||c=='[') {
        if(st < pt) {
            if(pt+1>=N) return -2;
            int v = st + pw[7] * (pt + 1) + pw[14] * (cnt + 1) + pw[21] * k;
            return v;
        }
        else { // pt < st case
            if(cnt==1) {
                int k2 = (c=='<'?1:0);
                if(k==k2) {
                    if(st+1>=N) return -1;
                    int v = st+1 + pw[7] * (st+1) + pw[14] * 0 + pw[21] * 0;
                    return v;
                }
                else return -2;
            }
            else {
                if(pt-1<0) return -2;
                assert(cnt-1>0);
                int v = st + pw[7] * (pt - 1) + pw[14] * (cnt - 1) + pw[21] *k;
                return v;
            }
        }
    }
    else { // c == '>' || c == ']'
        if(st<pt) {
            if(cnt==1) {
                int k2 = (c=='>'?1:0);
                if(k==k2) {
                    if(st+1>=N) return -1;
                    int v = st+1 + pw[7] * (st+1) + pw[14] * 0 + pw[21] * 0;
                    return v;
                }
                else return -2;
            }
            else {
                if(pt+1>=N) return -2;
                assert(cnt-1>0);
                int v = st + pw[7] * (pt+1) + pw[14] * (cnt-1) + pw[21] * k;
                return v;
            }
        }
        else { // pt < st
            if(pt-1<0) return -2;
            int v = st + pw[7] * (pt-1) + pw[14] * (cnt+1) + pw[21] * k;
            return v;
        }
    }
}
/*
signed main() {
    cin >> s;
    int cnt = 15000;
    int M = 0;
    while(cnt--) {
        M = Memory(s.length(), M);
        cout << M << '\n';
        if(M==-1) cout << "Right\n";
        else if(M==-2) cout << "Wrong\n";
        if(M==-1||M==-2) break;
    }
}
*/


/*
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int Memory(int N, int M);

#define MAX_N 100
#define FORMAT_S "%101s"
#define LENGTH_S 102
#define LIMIT_M 4194304  // 2^22
#define MAX_NUM_DAYS 15000

static int N, Q;
static char S[LENGTH_S];

static void Wrong(int message) {
  printf("Wrong Answer [%d]\n", message);
  exit(0);
}

static int get_called;
static int get_I;

char Get(int I) {
  if (get_called) {
    Wrong(2);
  }
  get_called = 1;
  get_I = I;
  if (!(1 <= I && I <= N)) {
    Wrong(3);
  }
  return S[I - 1];
}

int main(void) {
  int M;
  int test_index;
  int num_days;

  if (scanf("%d%d", &N, &Q) != 2) {
    fprintf(stderr, "error: cannot read N, Q\n");
    exit(1);
  }
  if (!(1 <= N && N <= MAX_N)) {
    fprintf(stderr, "error: N is out of bounds\n");
    exit(1);
  }
  if (Q < 0) {
    fprintf(stderr, "error: Q is out of bounds\n");
    exit(1);
  }

  for (test_index = 0; test_index < Q; ++test_index) {
    if (scanf(FORMAT_S, S) != 1) {
      fprintf(stderr, "error: cannot read S\n");
      exit(1);
    }
    if (N != (int)strlen(S)) {
      fprintf(stderr, "error: the length of S is not N\n");
      exit(1);
    }
    num_days = 0;
    M = 0;
    for (; ; ) {
      get_called = 0;
      get_I = 0;
      M = Memory(N, M);
      if (!((0 <= M && M < LIMIT_M) || M == -1 || M == -2)) {
        Wrong(1);
      }
      if (M == -1 || M == -2) {
        break;
      }
      if (++num_days >= MAX_NUM_DAYS) {
        Wrong(5);
      }
    }
    printf("%d\n", M);
  }

  return 0;
}

*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 60 / 60