Submission #56964

#	Time	Username	Problem	Language	Result	Execution time	Memory
56964		Diuven	기억 압축 (JOI15_memory)	C++11	100 / 100	3556 ms	276924 KiB

memory

#include "Memory_lib.h"
#include <iostream>
using namespace std;

int my_get(int x, int n){
    x=min(x, n);
    x=max(x, 1);
    return Get(x);
}

int f2(int a){
    return a + (1<<20);
}
int f3(int a, int b, int c, int d){
    return a + (b<<7) + (c<<14) + (d<<20) + (1<<21);
}

int solve1(int n, int m){
    int pos, cnt;
    pos=m%(1<<7); m/=(1<<7);
    cnt=m;
    // cout<<"1: "<<pos<<' '<<cnt<<'\n';

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

    char c=my_get(++pos, n);
    
    cnt += (c=='[' || c=='<') ? 1 : -1;

    if(cnt<0 || cnt>n/2) return -2;

    return pos + (cnt<<7);
}


int solve2(int n, int m){
    int pos=m%(1<<7);
    // cout<<"2: "<<pos<<'\n';
    char c=my_get(pos, n);
    if(c=='<' || c=='[') return f3(pos, pos, 0, (c=='<' ? 1 : 0));
    else if(pos<n) return f2(pos+1);
    else return -1;
}

int solve3(int n, int m){
    // piv, now, type, cnt
    // => 7+7+1+6 => 21
    int piv, now, cnt, type;
    piv=m%(1<<7); m/=(1<<7);
    now=m%(1<<7); m/=(1<<7);
    cnt=m%(1<<6); m/=(1<<6);
    type=m%2; m/=2;

    // cout<<"3: "<<piv<<' '<<now<<' '<<cnt<<' '<<type<<'\n';

    if(piv>now) return -2;
    if(now>n) return -2;
    if(cnt>n/2) return -2;

    char c=my_get(now, n);

    cnt += (c=='[' || c=='<') ? 1 : -1;

    if(cnt==0){
        int check=(c=='>' ? 1 : 0);
        if(type!=check) return -2;
        else return f2(piv+1);
    }
    else return f3(piv, now+1, cnt, type);
}

int Memory(int n, int m){
    int res;
    if(m<(1<<14)){
        res=solve1(n,m);
    }
    else if(m<(1<<21)){
        res=solve2(n,m);
    }
    else{
        res=solve3(n,m);
    }
    
    if(res<-2 || (1<<22)<=res) res=-2;
    return res;
}

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