oj.uz

Submission #297976

# Submission time Handle Problem Language Result Execution time Memory
297976 2020-09-12T08:56:02 Z Autoratch Ancient Books (IOI17_books) C++14
12 / 100
 975 ms 1064 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,tuple<int,int,int> > 

const int N = 2000;

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

long long minimum_walk(std::vector<int> p, int s) 
{
    n = p.size();
    vector<int> v;
    for(int i = 0;i < n;i++) v.push_back(i);
    int cnt = 0;
    if(n==4) for(int i = 0;i <= 4;i++) for(int j = 0;j <= 4;j++) for(int k = 0;k <= 4;k++) for(int l = 0;l <= 4;l++) 
    {
        vector<int> v = {i,j,k,l};
        ma[cnt] = v;
        mb[v] = cnt;
        cnt++;
    }
    else if(n==3) for(int i = 0;i <= 3;i++) for(int j = 0;j <= 3;j++) for(int k = 0;k <= 3;k++)
    {
        vector<int> v = {i,j,k};
        ma[cnt] = v;
        mb[v] = cnt;
        cnt++;
 
    }
    else if(n==2) for(int i = 0;i <= 2;i++) for(int j = 0;j <= 2;j++)
    {
        vector<int> v = {i,j};
        ma[cnt] = v;
        mb[v] = cnt;
        cnt++;
    }
    else for(int i = 0;i <= 1;i++)
    {
        vector<int> v = {i};
        ma[cnt] = v;
        mb[v] = cnt;
        cnt++;
    }   
    for(int i = 0;i < N;i++) for(int j = 0;j <= n;j++) for(int k = 0;k <= n;k++) res[i][j][k] = INT_MAX;
    res[mb[p]][s][n] = 0;
    q.push({0,{mb[p],s,n}});
    while(!q.empty())
    {
        auto [per,id,hn] = q.top().second;
        q.pop();
        if(visited[per][id][hn]) continue;
        visited[per][id][hn] = true;
        vector<int> now = ma[per];
        for(int i = 0;i < n;i++) if(res[per][id][hn]+abs(id-i)<res[per][i][hn])
        {
            res[per][i][hn] = res[per][id][hn]+abs(id-i);
            q.push({res[per][i][hn],{per,i,hn}});
        }
        vector<int> nx = now;
        int hnd = nx[id];
        nx[id] = hn;
        if(res[per][id][hn]<res[mb[nx]][id][hnd])
        {
            res[mb[nx]][id][hnd] = res[per][id][hn];
            q.push({res[mb[nx]][id][hnd],{mb[nx],id,hnd}});
        }
    }
    vector<int> ans;
    for(int i = 0;i < n;i++) ans.push_back(i);
    return res[mb[ans]][0][n];
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         auto [per,id,hn] = q.top().second;
      |              ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 1 ms 640 KB Output is correct
18 Correct 1 ms 640 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 1 ms 640 KB Output is correct
18 Correct 1 ms 640 KB Output is correct
19 Runtime error 970 ms 1064 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 1 ms 640 KB Output is correct
18 Correct 1 ms 640 KB Output is correct
19 Runtime error 970 ms 1064 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 975 ms 872 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 1 ms 640 KB Output is correct
18 Correct 1 ms 640 KB Output is correct
19 Runtime error 970 ms 1064 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -