oj.uz

답안 #677392

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677392 2023-01-03T07:34:52 Z qwerasdfzxcl 기억 압축 (JOI15_memory) C++17
100 / 100
 2166 ms 284296 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2065 ms 284108 KB Output is correct
2 Correct 2081 ms 284296 KB Output is correct
3 Correct 2029 ms 284004 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2065 ms 284108 KB Output is correct
2 Correct 2081 ms 284296 KB Output is correct
3 Correct 2029 ms 284004 KB Output is correct
4 Correct 2036 ms 284036 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2065 ms 284108 KB Output is correct
2 Correct 2081 ms 284296 KB Output is correct
3 Correct 2029 ms 284004 KB Output is correct
4 Correct 2036 ms 284036 KB Output is correct
5 Correct 2057 ms 284108 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2065 ms 284108 KB Output is correct
2 Correct 2081 ms 284296 KB Output is correct
3 Correct 2029 ms 284004 KB Output is correct
4 Correct 2036 ms 284036 KB Output is correct
5 Correct 2057 ms 284108 KB Output is correct
6 Correct 2044 ms 284164 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2166 ms 284016 KB Output is correct

Subtask #6
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2065 ms 284108 KB Output is correct
2 Correct 2081 ms 284296 KB Output is correct
3 Correct 2029 ms 284004 KB Output is correct
4 Correct 2036 ms 284036 KB Output is correct
5 Correct 2057 ms 284108 KB Output is correct
6 Correct 2044 ms 284164 KB Output is correct
7 Correct 2166 ms 284016 KB Output is correct
8 Correct 2087 ms 284196 KB Output is correct
9 Correct 2105 ms 284036 KB Output is correct