oj.uz

Submission #297958

# Submission time Handle Problem Language Result Execution time Memory
297958 2020-09-12T08:25:18 Z Autoratch Ancient Books (IOI17_books) C++14
0 / 100
 1 ms 384 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,pair<int,int> > 

const int N = 4;
const int M = 30;

int n;
map<int,vector<int> > ma;
map<vector<int>,int> mb;
int res[M][N];
priority_queue<pii,vector<pii>,greater<pii> > q;
bool visited[M][M];

long long minimum_walk(std::vector<int> p, int s) 
{
    n = 4;
    vector<int> v;
    for(int i = 0;i < n;i++) v.push_back(i);
    int cnt = 0;
    do
    {
        ma[cnt] = v;
        mb[v] = cnt;
        cnt++;
    }while(next_permutation(v.begin(),v.end()));
    for(int i = 0;i < M;i++) for(int j = 0;j < n;j++) res[i][j] = INT_MAX;
    res[mb[p]][s] = 0;
    q.push({0,{mb[p],s}});
    while(!q.empty())
    {
        int per = q.top().second.first,id = q.top().second.second;
        q.pop();
        if(visited[per][id]) continue;
        visited[per][id] = true;
        vector<int> now = ma[per];
        for(int i = 0;i < 4;i++) if(res[per][id]+abs(id-i)<res[per][i])
        {
            res[per][i] = res[per][id]+abs(id-i);
            q.push({res[per][i],{per,i}});
        }
        for(int i = 0;i < 4;i++) 
        {
            vector<int> nx = now;
            swap(nx[i],nx[id]);
            if(res[per][id]+abs(id-i)*2<res[mb[nx]][i])
            {
                res[mb[nx]][i] = res[per][id]+abs(id-i);
                q.push({res[mb[nx]][i],{mb[nx],i}});
            }
        }
    }
    return res[0][0];
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '3304', found: '425'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
4 Halted 0 ms 0 KB -