oj.uz

Submission #56964

# Submission time Handle Problem Language Result Execution time Memory
56964 2018-07-13T11:12:29 Z Diuven None (JOI15_memory) C++11
100 / 100
 3556 ms 276924 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2707 ms 276764 KB Output is correct
2 Correct 3506 ms 276764 KB Output is correct
3 Correct 2948 ms 276820 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2707 ms 276764 KB Output is correct
2 Correct 3506 ms 276764 KB Output is correct
3 Correct 2948 ms 276820 KB Output is correct
4 Correct 3047 ms 276820 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2707 ms 276764 KB Output is correct
2 Correct 3506 ms 276764 KB Output is correct
3 Correct 2948 ms 276820 KB Output is correct
4 Correct 3047 ms 276820 KB Output is correct
5 Correct 3355 ms 276832 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2707 ms 276764 KB Output is correct
2 Correct 3506 ms 276764 KB Output is correct
3 Correct 2948 ms 276820 KB Output is correct
4 Correct 3047 ms 276820 KB Output is correct
5 Correct 3355 ms 276832 KB Output is correct
6 Correct 3093 ms 276832 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3095 ms 276892 KB Output is correct

Subtask #6
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2707 ms 276764 KB Output is correct
2 Correct 3506 ms 276764 KB Output is correct
3 Correct 2948 ms 276820 KB Output is correct
4 Correct 3047 ms 276820 KB Output is correct
5 Correct 3355 ms 276832 KB Output is correct
6 Correct 3093 ms 276832 KB Output is correct
7 Correct 3095 ms 276892 KB Output is correct
8 Correct 3556 ms 276892 KB Output is correct
9 Correct 3338 ms 276924 KB Output is correct