oj.uz

Submission #56919

# Submission time Handle Problem Language Result Execution time Memory
56919 2018-07-13T07:33:57 Z 노영훈(#1634) None (JOI15_memory) C++11
40 / 100
 3833 ms 276912 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(n%2==1) return -2;

    int mode=m%2; m/=2;

    if(mode==0){
        int pos=m%(1<<7); m/=(1<<7);
        int cnt1=m, cnt2=0;
        if(pos>=n) return cnt1==0 ? -1 : -2;

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

        for(; sz>0; sz--){
            if(!(((stk&(1<<(sz-1)))!=0) ^ ((stk&(1<<15))!=0))) continue;
            else break;
        }
        // cout<<"STACK: \n";
        // for(int i=0; i<16; i++)
        //     cout<<((stk&(1<<i))!=0)<<' ';
        // cout<<'\n';


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

        char c=Get(++pos);

        if(c=='<'){
            if(sz>=15) return -2;
            stk|=(1<<(sz++));
        }
        if(c=='>'){
            if(sz==0 || (stk&(1<<(sz-1)))==0) return -2;
            sz--;
        }
        if(c=='['){
            if(sz>=15) return -2;
            stk-=stk&(1<<sz++);
        }
        if(c==']'){
            if(sz==0 || (stk&(1<<(sz-1)))!=0) return -2;
            sz--;
        }
        for(int i=sz; i<16; i++){
            if(sz==0 || (stk&(1<<(sz-1)))==0) stk|=(1<<i);
            else stk-=(stk&(1<<i));
        }

        return 1 + (pos<<1) + (stk<<6);
    }
    return -1;
}


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

# Verdict Execution time Memory Grader output
1 Correct 3013 ms 276672 KB Output is correct
2 Correct 3177 ms 276748 KB Output is correct
3 Correct 3833 ms 276888 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3013 ms 276672 KB Output is correct
2 Correct 3177 ms 276748 KB Output is correct
3 Correct 3833 ms 276888 KB Output is correct
4 Correct 3351 ms 276908 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3013 ms 276672 KB Output is correct
2 Correct 3177 ms 276748 KB Output is correct
3 Correct 3833 ms 276888 KB Output is correct
4 Correct 3351 ms 276908 KB Output is correct
5 Correct 3808 ms 276912 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3013 ms 276672 KB Output is correct
2 Correct 3177 ms 276748 KB Output is correct
3 Correct 3833 ms 276888 KB Output is correct
4 Correct 3351 ms 276908 KB Output is correct
5 Correct 3808 ms 276912 KB Output is correct
6 Correct 3095 ms 276912 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3484 ms 276912 KB Output is correct

Subtask #6
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3013 ms 276672 KB Output is correct
2 Correct 3177 ms 276748 KB Output is correct
3 Correct 3833 ms 276888 KB Output is correct
4 Correct 3351 ms 276908 KB Output is correct
5 Correct 3808 ms 276912 KB Output is correct
6 Correct 3095 ms 276912 KB Output is correct
7 Correct 3484 ms 276912 KB Output is correct
8 Correct 3066 ms 276912 KB Output is correct
9 Incorrect 3536 ms 276912 KB Wrong Answer [6]