Submission #775886

#	Time	Username	Problem	Language	Result	Execution time	Memory
775886		peteza	Ancient Books (IOI17_books)	C++14	12 / 100	1541 ms	1048576 KiB

books

#include <bits/stdc++.h>
#include "books.h"

struct state {
    std::vector<int> cur;
    int cpos, car;
};

long long minimum_walk(std::vector<int> p, int s) {
    int cur = 0;
    state start;
    start.cur = p; start.cpos = s; start.car = -1;
    std::queue<std::pair<int, state>> q;
    q.emplace(0, start);
    while(!q.empty()) {
        auto e = q.front(); q.pop();
        auto dat = e.second;
        if(std::is_sorted(dat.cur.begin(), dat.cur.end()) && dat.cpos == s && dat.car == -1)
            return e.first;
        std::swap(dat.cur[dat.cpos], dat.car);
        q.emplace(e.first, dat);
        std::swap(dat.cur[dat.cpos], dat.car);
        if(dat.cpos != 0) {
            dat.cpos--;
            q.emplace(e.first+1, dat);
            dat.cpos++;
        }
        if(dat.cpos != p.size()-1) {
            dat.cpos++;
            q.emplace(e.first+1, dat);
            dat.cpos--;
        }
    }
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if(dat.cpos != p.size()-1) {
      |            ~~~~~~~~~^~~~~~~~~~~~~
books.cpp:10:9: warning: unused variable 'cur' [-Wunused-variable]
   10 |     int cur = 0;
      |         ^~~
books.cpp:11:11: warning: control reaches end of non-void function [-Wreturn-type]
   11 |     state start;
      |           ^~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30