oj.uz

답안 #56904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56904 2018-07-13T06:44:37 Z 노영훈(#1634) 기억 압축 (JOI15_memory) C++11
25 / 100
 4109 ms 276860 KB 
#include "Memory_lib.h"
#include <iostream>
using namespace std;

int f1(char c){
    if(c=='<') return 1;
    if(c=='>') return -1;
    return 0;
}
int f2(char c){
    if(c=='[') return 1;
    if(c==']') return -1;
    return 0;
}

int solve(int n, int m) {
    if(m==0) m=15;
    int sz=m%16; m/=16;

    if(sz==15){
        int pos=m%(1<<7); m/=(1<<7);
        int cnt1=m, cnt2=0;

        if(pos>=n) return cnt1==0 ? -1 : -2;
        if(cnt1>n/2) return -2;

        char c=Get(++pos);
        cnt1+=f1(c), cnt2+=f2(c);
        if(cnt1<0 || cnt2<0) return -2;
        if(cnt2>0){
            sz=cnt1+cnt2;
            int stk=0;
            for(int i=0; i<cnt1; i++)
                stk|=(1<<i);
            return sz + (pos<<4) + (stk<<9);
        }
        else{
            return sz + (pos<<4) + (cnt1<<11);
        }
    }
    else{
        int pos=m%32; m/=32;
        int stk=m;

        if(pos>=n) return sz==0 ? -1 : -2;

        char c=Get(++pos);

        if(c=='<'){
            if(sz>=12) return -2;
            stk|=(1<<(sz++));
        }
        if(c=='>'){
            if(sz==0 || (stk&(1<<(sz-1)))==0) return -2;
            sz--;
        }
        if(c=='['){
            if(sz>=12) return -2;
            stk-=stk&(1<<sz++);
        }
        if(c==']'){
            if(sz==0 || (stk&(1<<(sz-1)))!=0) return -2;
            sz--;
        }

        return sz + (pos<<4) + (stk<<9);
    }


    
    return m;
}


int Memory(int n, int m){
    int ans=solve(n,m);
    // if(ans<-2 || ans>(1<<22))
    //     cout<<n<<' '<<m<<": "<<ans<<'\n';
    return ans;
}



/*
int Memory(int n, int m) {
    int cnt1=0, cnt2=0, pos=0;
    
    cnt1=m%(1<<7); m/=(1<<7);
    cnt2=m%(1<<7); m/=(1<<7);
    pos=m;

    // cout<<cnt1<<' '<<cnt2<<' '<<pos<<'\n';

    if(pos>=n){
        return (pos==n && cnt1==0 && cnt2==0) ? -1 : -2;
    }

    // if(pos+1<=0 || n<pos+1) cout<<pos<<' '<<n<<"\n";
    char c=Get(++pos);

    if(c=='<') cnt1++;
    if(c=='>') cnt1--;
    if(c=='[') cnt2++;
    if(c==']') cnt2--;

    if(cnt1<0 || cnt2<0) return -2;

    m=(pos<<14) + (cnt2<<7) + cnt1;

    return m;
}

*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4109 ms 276856 KB Output is correct
2 Correct 3979 ms 276856 KB Output is correct
3 Correct 3713 ms 276856 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4109 ms 276856 KB Output is correct
2 Correct 3979 ms 276856 KB Output is correct
3 Correct 3713 ms 276856 KB Output is correct
4 Correct 3835 ms 276856 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4109 ms 276856 KB Output is correct
2 Correct 3979 ms 276856 KB Output is correct
3 Correct 3713 ms 276856 KB Output is correct
4 Correct 3835 ms 276856 KB Output is correct
5 Correct 3787 ms 276860 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4109 ms 276856 KB Output is correct
2 Correct 3979 ms 276856 KB Output is correct
3 Correct 3713 ms 276856 KB Output is correct
4 Correct 3835 ms 276856 KB Output is correct
5 Correct 3787 ms 276860 KB Output is correct
6 Incorrect 111 ms 276860 KB Wrong Answer [1]

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 276860 KB Wrong Answer [1]

Subtask #6
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4109 ms 276856 KB Output is correct
2 Correct 3979 ms 276856 KB Output is correct
3 Correct 3713 ms 276856 KB Output is correct
4 Correct 3835 ms 276856 KB Output is correct
5 Correct 3787 ms 276860 KB Output is correct
6 Incorrect 111 ms 276860 KB Wrong Answer [1]