oj.uz

Submission #677409

# Submission time Handle Problem Language Result Execution time Memory
677409 2023-01-03T08:12:55 Z jhwest2 None (JOI15_memory) C++17
100 / 100
 3745 ms 456520 KB 
#include "Memory_lib.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    const int N = 101;
    const int B = 1 << 22;

    const int D1 = 101;
    const int D2 = 101 * 101;
    const int D3 = 101 * 101 * 101;
    const int D4 = 101 * 101 * 101 * 101;

    bool init = false;

    int sz = 0;
    int a[B];
    int mp[2 * D4];

    void initialize(int n) {
        for (int rev = 0; rev <= 1; rev++)
            for (int s = 1; s <= n; s++)
                for (int t = 1; t <= n; t++)
                    for (int x = 0; x <= n / 2; x++)
                        for (int y = 0; y <= n / 2; y++)
                            if (((!rev && s <= t) || (rev && s >= t)) && (x + y) % 2 == abs(t - s) % 2 && x + y <= abs(t - s)) 
                                a[sz++] = y + D1 * x + D2 * t + D3 * s + D4 * rev;
        
        for (int i = 0; i < sz; i++) 
            mp[a[i]] = i;
    }
}
int Memory(int n, int m) {
    if (!init) {
        init = true;
        initialize(n);
    }
    if (m >= sz)
        return -2;

    auto val = a[m];
    int y = val % D1; val /= D1;
    int x = val % D1; val /= D1;
    int t = val % D1; val /= D1;
    int s = val % D1; val /= D1;
    int rev = val;

    char c = Get(t);

    if (!rev) {
        if (s == t && (c == '>' || c == ']')) {
            if (s != n) {
                s = s + 1;
                t = t + 1;
                return mp[y + D1 * x + D2 * t + D3 * s + D4 * rev];
            }
            else {
                rev = 1;
                s = n;
                t = n;
                return mp[y + D1 * x + D2 * t + D3 * s + D4 * rev];
            }
        }
        else {
            if (c == '[')
                ++x;
            if (c == ']')
                --x;
            if (c == '<')
                ++y;
            if (c == '>')
                --y;

            if (x < 0 || y < 0 || x > n / 2 || y > n / 2)
                return -2;
            else {
                if (x != 0 || y != 0) {
                    t = t + 1;

                    if (t == n + 1)
                        return -2;
                    else 
                        return mp[y + D1 * x + D2 * t + D3 * s + D4 * rev];
                }
                else {
                    if (s != n) {
                        s = s + 1;
                        t = s;
                        x = 0;
                        y = 0;
                        return mp[y + D1 * x + D2 * t + D3 * s + D4 * rev];
                    }
                    else {
                        rev = 1;
                        s = n;
                        t = n;
                        x = 0;
                        y = 0;
                        return mp[y + D1 * x + D2 * t + D3 * s + D4 * rev];
                    }
                }
            }
        }
    }
    else {
        if (s == t && (c == '<' || c == '[')) {
            if (s != 1) {
                s = s - 1;
                t = t - 1;
                return mp[y + D1 * x + D2 * t + D3 * s + D4 * rev];
            }
            else 
                return -1;
        }
        else {
            if (c == ']')
                ++x;
            if (c == '[')
                --x;
            if (c == '>')
                ++y;
            if (c == '<')
                --y;

            if (x < 0 || y < 0 || x > n / 2 || y > n / 2)
                return -2;
            else {
                if (x != 0 || y != 0) {
                    t = t - 1;

                    if (t == 0)
                        return -2;
                    else 
                        return mp[y + D1 * x + D2 * t + D3 * s + D4 * rev];
                }
                else {
                    if (s != 1) {
                        s = s - 1;
                        t = s;
                        x = 0;
                        y = 0;
                        return mp[y + D1 * x + D2 * t + D3 * s + D4 * rev];
                    }
                    else
                        return -1;
                }
            }
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2150 ms 284108 KB Output is correct
2 Correct 2104 ms 284072 KB Output is correct
3 Correct 2197 ms 284612 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2150 ms 284108 KB Output is correct
2 Correct 2104 ms 284072 KB Output is correct
3 Correct 2197 ms 284612 KB Output is correct
4 Correct 2163 ms 285344 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2150 ms 284108 KB Output is correct
2 Correct 2104 ms 284072 KB Output is correct
3 Correct 2197 ms 284612 KB Output is correct
4 Correct 2163 ms 285344 KB Output is correct
5 Correct 2106 ms 288436 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2150 ms 284108 KB Output is correct
2 Correct 2104 ms 284072 KB Output is correct
3 Correct 2197 ms 284612 KB Output is correct
4 Correct 2163 ms 285344 KB Output is correct
5 Correct 2106 ms 288436 KB Output is correct
6 Correct 2192 ms 291436 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3745 ms 456520 KB Output is correct

Subtask #6
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2150 ms 284108 KB Output is correct
2 Correct 2104 ms 284072 KB Output is correct
3 Correct 2197 ms 284612 KB Output is correct
4 Correct 2163 ms 285344 KB Output is correct
5 Correct 2106 ms 288436 KB Output is correct
6 Correct 2192 ms 291436 KB Output is correct
7 Correct 3745 ms 456520 KB Output is correct
8 Correct 3633 ms 450924 KB Output is correct
9 Correct 3648 ms 456348 KB Output is correct