Submission #677392

#	Time	Username	Problem	Language	Result	Execution time	Memory
677392		qwerasdfzxcl	기억 압축 (JOI15_memory)	C++17	100 / 100	2166 ms	284296 KiB

memory

#include "Memory_lib.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct Data{
    int x, y, z, w;
    Data(){}
    Data(int _x, int _y, int _z, int _w): x(_x), y(_y), z(_z), w(_w) {}
};

Data decode(int M){
    return Data((M&(127<<15))>>15, (M&(127<<8))>>8, (M&(127<<1))>>1, M&1);
}

int encode(int x, int y, int z, int w){
    //printf("%d %d %d %d / M = %d\n", x, y, z, w, (x<<15) | (y<<8) | (z<<1) | w);
    //assert(((x<<15) | (y<<8) | (z<<1) | w) < (1<<22));
    return (x<<15) | (y<<8) | (z<<1) | w;
}

int myabs(int x){return x<0?-x:x;}

bool valid(int s, int cur, int sum, int typ, int N){
    return s>=0 && s<=N+1 && cur>=0 && cur<=N+1 && myabs(s-cur) >= sum;
}

int Memory(int N, int M) {
    if (M==0) return encode(1, 1, 0, 0);
    auto [s, cur, sum, typ] = decode(M);

    if (!valid(s, cur, sum, typ, N)) return 0;

    //printf(" %d %d %d %d\n", s, cur, sum, typ);
    if (s==N+1) return -1;
    if (cur >= N+1 || cur <= 0) return -2;

    char x = Get(cur);
    if (s==cur){
        if (x=='>' || x==']') return encode(s, s-1, 1, x==']');
        return encode(s, s+1, 1, x=='[');
    }

    if ((x=='>' || x==']') == (s<cur)) sum -= 1;
    else sum += 1;

    //printf(" sum = %d\n", sum);

    if (sum==0){
        int typ2 = (x=='[' || x==']');
        //printf(" typ = %d / typ2 = %d\n", typ, typ2);
        if (typ==typ2) return encode(s+1, s+1, 0, 0);
        return -2;
    }

    int delta = (s<cur)?1:-1;
    return encode(s, cur+delta, sum, typ);
}

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