Submission #915145

#	Time	Username	Problem	Language	Result	Execution time	Memory
915145		nightfal	Ancient Books (IOI17_books)	C++14	50 / 100	101 ms	18900 KiB

books

#include <cstdio>
#include <vector>
#include <cassert>
#include <cstdlib>

using namespace std;

bool isSubtask3(int s) {return s==0;}

long long subtask3(vector<int> p, int s) {
    int n = p.size(), last = 0;
    long long total = 0;

    for(int i=s; i<n; i++) {
        if (i==p[i]) continue;
        if(i>last) total += (i-last)*2;
        total += abs(p[i]-i);
        last = max(last,p[i]);
    }
	return total;
}

long long fulltask(vector<int> p, int s) {

    int n = p.size(), left = s-1, right = s, leftmost = s-1, rightmost = s;
    long long total=0, sumL=0, sumR=0, moveL=1, moveR=0;

    while(0<=left || right<=n-1) {
        printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
        printf("left=%d, right=%d, leftmost=%d, rightmost=%d\n\n",left,right,leftmost,rightmost);

        if(right <= n-1 && (moveR < moveL || moveR == moveL && right <= rightmost)) {
            if(rightmost < right) moveR++;
            sumR += abs(p[right]-right);
            rightmost = max(rightmost,right);
            rightmost = max(rightmost,p[right]);    
            leftmost  = min(leftmost, p[right]);
            if (leftmost <= left) {moveL = 0; total+=sumR+moveR; moveR=0; sumR=0;}
            right++;
        } 
        else if(0 <= left && (moveR >= moveL || moveR == moveL && right > rightmost)) {
            if (left < leftmost) moveL++;
            sumL += abs(p[left]-left); 
            leftmost  = min(leftmost,left);
            leftmost  = min(leftmost, p[left]);
            rightmost = min(rightmost,p[left]);
            if (right <= rightmost) {moveR = 0; total+=sumL+moveL; moveL=0; sumL=0;}            
            left--;
        }
    }
    printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
    printf("left=%d, right%d, leftmost=%d, rightmost=%d\n",left,right,leftmost,rightmost);
 
    if(sumL) total += sumL + moveL; // ??
    if(sumR) total += sumR + moveR; // ??
    return total;
}

long long minimum_walk(std::vector<int> p, int s) {
    if (isSubtask3(s)) return subtask3(p,0);
    // return fulltask(p,s);
}

long long subtask3_old(vector<int> p, int s) {
    int n = p.size(), last = 0;
    long long total = 0;

    for(int i=0; i<n; i++) {
        if (i==p[i]) continue;
        if(i>last) total += (i-last)*2;
        total += abs(p[i]-i);

        last = max(last,i);
        int idx = p[i]; p[i] = i;
        while(idx!=i) {
            last = max(last,idx);
            total += abs(p[idx]-idx); 
            int prevIdx = idx; 
            idx = p[idx];
            p[prevIdx] = prevIdx;
        }
    }
	return total;
}

Compilation message (stderr)

books.cpp: In function 'long long int fulltask(std::vector<int>, int)':
books.cpp:29:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   29 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                       ~^                                          ~~~~~
      |                        |                                          |
      |                        int                                        long long int
      |                       %lld
books.cpp:29:33: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   29 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                ~^                                       ~~~~
      |                                 |                                       |
      |                                 int                                     long long int
      |                                %lld
books.cpp:29:42: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   29 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                         ~^                                   ~~~~
      |                                          |                                   |
      |                                          int                                 long long int
      |                                         %lld
books.cpp:29:52: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
   29 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                                   ~^                              ~~~~~
      |                                                    |                              |
      |                                                    int                            long long int
      |                                                   %lld
books.cpp:29:62: warning: format '%d' expects argument of type 'int', but argument 6 has type 'long long int' [-Wformat=]
   29 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                                             ~^                          ~~~~~
      |                                                              |                          |
      |                                                              int                        long long int
      |                                                             %lld
books.cpp:32:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   32 |         if(right <= n-1 && (moveR < moveL || moveR == moveL && right <= rightmost)) {
      |                                              ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
books.cpp:41:64: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   41 |         else if(0 <= left && (moveR >= moveL || moveR == moveL && right > rightmost)) {
      |                                                 ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
books.cpp:51:20: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   51 |     printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                   ~^                                          ~~~~~
      |                    |                                          |
      |                    int                                        long long int
      |                   %lld
books.cpp:51:29: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   51 |     printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                            ~^                                       ~~~~
      |                             |                                       |
      |                             int                                     long long int
      |                            %lld
books.cpp:51:38: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   51 |     printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                     ~^                                   ~~~~
      |                                      |                                   |
      |                                      int                                 long long int
      |                                     %lld
books.cpp:51:48: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
   51 |     printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                               ~^                              ~~~~~
      |                                                |                              |
      |                                                int                            long long int
      |                                               %lld
books.cpp:51:58: warning: format '%d' expects argument of type 'int', but argument 6 has type 'long long int' [-Wformat=]
   51 |     printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                                         ~^                          ~~~~~
      |                                                          |                          |
      |                                                          int                        long long int
      |                                                         %lld
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^

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