oj.uz

답안 #57144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57144 2018-07-14T07:01:49 Z gs13105 기억 압축 (JOI15_memory) C++17
100 / 100
 4335 ms 277028 KB 
#include "Memory_lib.h"
 
const int spos_inf = (1 << 7) - 1;
 
inline int extract(int x, int off, int siz)
{
    return x >> off & (1 << siz) - 1;
}
 
int Memory(int N, int M) {
    if(N % 2 == 1)
        return -2;
 
    int cpos = extract(M, 0, 7);
    int spos = extract(M, 7, 7);
    int snum = extract(M, 14, 6);
    int ctyp = extract(M, 20, 1);
    int runs = extract(M, 21, 1);
 
    spos = ~spos & (1 << 7) - 1;
 
    if(cpos >= N || spos != spos_inf && (spos >= cpos || snum > N / 2))
        return -2;
 
    if(runs == 0)
    {
        if(spos == spos_inf)
        {
            char c = Get(cpos + 1);
            if(c == '<' || c == '[')
                cpos++;
            else
            {
                if(cpos == 0)
                    return -2;
 
                spos = cpos - 1;
                snum = 0;
                ctyp = (c == '>') ? 0 : 1;
            }
        }
        else
        {
            char c = Get(spos + 1);
 
            if(snum == 0 && (c == '<' || c == '['))
            {
                if(c == '<' && ctyp == 0 || c == '[' && ctyp == 1)
                {
                    cpos++;
                    spos = spos_inf;
                }
                else
                    return -2;
            }
            else
            {
                if(spos == 0)
                    return -2;
 
                spos--;
                if(c == '<' || c == '[')
                    snum--;
                else
                    snum++;
            }
        }
 
        if(cpos == N)
        {
            cpos = 0;
            spos = spos_inf;
            runs = 1;
        }
    }
    else
    {
        if(spos == spos_inf)
        {
            char c = Get(N - cpos);
            if(c == '>' || c == ']')
                cpos++;
            else
            {
                if(cpos == 0)
                    return -2;
 
                spos = cpos - 1;
                snum = 0;
                ctyp = (c == '<') ? 0 : 1;
            }
        }
        else
        {
            char c = Get(N - spos);
 
            if(snum == 0 && (c == '>' || c == ']'))
            {
                if(c == '>' && ctyp == 0 || c == ']' && ctyp == 1)
                {
                    cpos++;
                    spos = spos_inf;
                }
                else
                    return -2;
            }
            else
            {
                if(spos == 0)
                    return -2;
 
                spos--;
                if(c == '>' || c == ']')
                    snum--;
                else
                    snum++;
            }
        }
 
        if(cpos == N)
            return -1;
    }
 
    spos = ~spos & (1 << 7) - 1;
 
    return cpos + (spos << 7) + (snum << 14) + (ctyp << 20) + (runs << 21);
}

Compilation message

memory.cpp: In function 'int extract(int, int, int)':
memory.cpp:7:34: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
     return x >> off & (1 << siz) - 1;
                       ~~~~~~~~~~~^~~
memory.cpp: In function 'int Memory(int, int)':
memory.cpp:20:29: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
     spos = ~spos & (1 << 7) - 1;
                    ~~~~~~~~~^~~
memory.cpp:22:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if(cpos >= N || spos != spos_inf && (spos >= cpos || snum > N / 2))
                     ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
memory.cpp:48:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 if(c == '<' && ctyp == 0 || c == '[' && ctyp == 1)
                    ~~~~~~~~~^~~~~~~~~~~~
memory.cpp:99:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 if(c == '>' && ctyp == 0 || c == ']' && ctyp == 1)
                    ~~~~~~~~~^~~~~~~~~~~~
memory.cpp:124:29: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
     spos = ~spos & (1 << 7) - 1;
                    ~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2654 ms 276704 KB Output is correct
2 Correct 2758 ms 276732 KB Output is correct
3 Correct 2907 ms 276748 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2654 ms 276704 KB Output is correct
2 Correct 2758 ms 276732 KB Output is correct
3 Correct 2907 ms 276748 KB Output is correct
4 Correct 2909 ms 276760 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2654 ms 276704 KB Output is correct
2 Correct 2758 ms 276732 KB Output is correct
3 Correct 2907 ms 276748 KB Output is correct
4 Correct 2909 ms 276760 KB Output is correct
5 Correct 3967 ms 276980 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2654 ms 276704 KB Output is correct
2 Correct 2758 ms 276732 KB Output is correct
3 Correct 2907 ms 276748 KB Output is correct
4 Correct 2909 ms 276760 KB Output is correct
5 Correct 3967 ms 276980 KB Output is correct
6 Correct 4335 ms 276984 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2654 ms 276704 KB Output is correct
2 Correct 2758 ms 276732 KB Output is correct
3 Correct 2907 ms 276748 KB Output is correct
4 Correct 2909 ms 276760 KB Output is correct
5 Correct 3967 ms 276980 KB Output is correct
6 Correct 4335 ms 276984 KB Output is correct
7 Correct 4328 ms 276984 KB Output is correct
8 Correct 3454 ms 277028 KB Output is correct
9 Correct 2901 ms 277028 KB Output is correct