oj.uz

Submission #915893

# Submission time Handle Problem Language Result Execution time Memory
915893 2024-01-24T20:57:03 Z nightfal Ancient Books (IOI17_books) C++14
22 / 100
 866 ms 1048576 KB 
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <tuple>
#include <climits>

using namespace std;

bool isSubtask3(int s) {return s==0;}
bool isSubtask4(int n) {return n<=1000;}

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

    for(int i=s; dir==1 && i<=e || dir==-1 && i>=e; i += dir) {
        if (i==p[i]) continue;
        if (dir*(i-last) > 0) total += abs(i-last)*2;
        total += abs(p[i]-i);
        last = dir==1? max(last,p[i]):min(last,p[i]);
    }
	return total;
}
tuple<int,int,long long> extend(vector<int> p, int l, int r, int lmost, int rmost, int move) {
    int n = p.size();
    while(l> lmost || r < rmost) {
        int idx;
        if (l > max(lmost,0)) idx == --l;
        else if (r < min(rmost,n-1)) idx == ++r;
        move += abs(p[idx]-idx);
        lmost = min(lmost,p[idx]); 
        rmost = max(rmost,p[idx]);
    }
    return make_tuple(l,r,move);
} 
long long cal2(vector<int> p, int l, int r, int lmost, int rmost, long long move, vector<vector<long long>>& dp) {
    if (dp[l][r]) return dp[l][r];
    int n = p.size();
    tie(l,r,move) = extend(p,l,r,lmost,rmost,move);
    dp[l][r] = move;
    if (l>0) dp[l][r] = cal2(p,l-1,r,lmost,rmost,move,dp) + 2;
    if (r<n-1) dp[l][r] = min(dp[l][r],cal2(p,l,r+1,lmost,rmost,move,dp)+2);
    return move;
}
long long cal(vector<int> p, int l, int r, int lmost, int rmost, vector<vector<long long>>& dp) {
    // printf("l=%d, r=%d, lmost=%d, rmost=%d\n",l,r,lmost,rmost);
    // for(auto & row: dp) {for(long long elem: row) printf("%lld ",elem); printf("\n");}
    if (dp[l][r]!=LLONG_MAX) return dp[l][r];
    int n = p.size();
    long long temp1=LLONG_MAX, temp2=LLONG_MAX;
    if (l>0) {
        temp1 = abs(p[l-1]-(l-1));
        if(l-1 < lmost) temp1 += 2;
        int lmostN = min(l-1,p[l-1]);
        lmostN = min(lmost,lmostN);
        int rmostN = max(rmost,p[l-1]);
        temp1 += cal(p,l-1,r,lmostN,rmostN,dp); 
    }
    if (r<n-1) {
        temp2 = abs(p[r+1]-(r+1));
        if(r+1 > rmost) temp2 += 2;
        int lmostN = min(lmost,p[r+1]);
        int rmostN = max(r+1,p[r+1]);
        rmostN = max(rmost,rmostN);
        temp2 += cal(p,l,r+1,lmostN,rmostN,dp); 
    }
    dp[l][r] = min(temp1,temp2);
    // printf("dp[%d][%d]=%lld=min(%lld,%lld), \n",l,r,dp[l][r],temp1,temp2);
    return dp[l][r];
}

long long subtask4(vector<int> p, int s) {
    int n = p.size();
    long long move = 0;

    
    int start; for(start = 0; start < s; start++) if(start!=p[start]) break;
    int end; for(end = n-1; end > s; end--) if(end!=p[end]) break;
    for(int i = 0; i <= end-start; i++) p[i] = p[i+start]-start;
    s -= start; n = end-start+1; p.resize(n); 
    vector<vector<long long>> dp(n,vector<long long>(n,LLONG_MAX));
    dp[0][n-1]=0;
    // printf("s=%d\n",s);
    // printf("p: "); for(int elem: p) printf("%d ", elem); printf("\n");
    
    // for(auto &row: dp) {for(long long elem: row) printf("%lld ",elem); printf("\n");}
    int l=s, r=s, lmost = min(s,p[s]), rmost = max(s,p[s]);
    return cal(p,l,r,lmost,rmost,dp)+p[s];
}

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 && (left < 0 || 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*2; moveR=0; sumR=0;}
            right++;
        } 
        else if(0 <= left && (right > n-1 || 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*2; 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 (isSubtask4(p.size()))
    return subtask4(p,s);
    // if (isSubtask3(s)) return subtask3(p);
    // return fulltask(p,s);
}

Compilation message

books.cpp: In function 'long long int subtask3(std::vector<int>, int, int, int)':
books.cpp:18:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   18 |     for(int i=s; dir==1 && i<=e || dir==-1 && i>=e; i += dir) {
      |                  ~~~~~~~^~~~~~~
books.cpp: In function 'std::tuple<int, int, long long int> extend(std::vector<int>, int, int, int, int, int)':
books.cpp:30:35: warning: value computed is not used [-Wunused-value]
   30 |         if (l > max(lmost,0)) idx == --l;
      |                               ~~~~^~~~~~
books.cpp:31:42: warning: value computed is not used [-Wunused-value]
   31 |         else if (r < min(rmost,n-1)) idx == ++r;
      |                                      ~~~~^~~~~~
books.cpp: In function 'long long int subtask4(std::vector<int>, int)':
books.cpp:76:15: warning: unused variable 'move' [-Wunused-variable]
   76 |     long long move = 0;
      |               ^~~~
books.cpp: In function 'long long int fulltask(std::vector<int>, int)':
books.cpp:99:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   99 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                       ~^                                          ~~~~~
      |                        |                                          |
      |                        int                                        long long int
      |                       %lld
books.cpp:99:33: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   99 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                ~^                                       ~~~~
      |                                 |                                       |
      |                                 int                                     long long int
      |                                %lld
books.cpp:99:42: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   99 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                         ~^                                   ~~~~
      |                                          |                                   |
      |                                          int                                 long long int
      |                                         %lld
books.cpp:99:52: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
   99 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                                   ~^                              ~~~~~
      |                                                    |                              |
      |                                                    int                            long long int
      |                                                   %lld
books.cpp:99:62: warning: format '%d' expects argument of type 'int', but argument 6 has type 'long long int' [-Wformat=]
   99 |         printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                                             ~^                          ~~~~~
      |                                                              |                          |
      |                                                              int                        long long int
      |                                                             %lld
books.cpp:102:73: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  102 |         if(right <= n-1 && (left < 0 || moveR < moveL || moveR == moveL && right <= rightmost)) {
      |                                                          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
books.cpp:111:78: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  111 |         else if(0 <= left && (right > n-1 || moveR > moveL || moveR == moveL && right > rightmost)) {
      |                                                               ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
books.cpp:121:20: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  121 |     printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                   ~^                                          ~~~~~
      |                    |                                          |
      |                    int                                        long long int
      |                   %lld
books.cpp:121:29: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
  121 |     printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                            ~^                                       ~~~~
      |                             |                                       |
      |                             int                                     long long int
      |                            %lld
books.cpp:121:38: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
  121 |     printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                     ~^                                   ~~~~
      |                                      |                                   |
      |                                      int                                 long long int
      |                                     %lld
books.cpp:121:48: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
  121 |     printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
      |                                               ~^                              ~~~~~
      |                                                |                              |
      |                                                int                            long long int
      |                                               %lld
books.cpp:121:58: warning: format '%d' expects argument of type 'int', but argument 6 has type 'long long int' [-Wformat=]
  121 |     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 'std::tuple<int, int, long long int> extend(std::vector<int>, int, int, int, int, int)':
books.cpp:32:26: warning: 'idx' is used uninitialized in this function [-Wuninitialized]
   32 |         move += abs(p[idx]-idx);
      |                          ^

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 9 ms 12376 KB Output is correct
20 Correct 7 ms 12376 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 8 ms 12380 KB Output is correct
23 Correct 7 ms 12124 KB Output is correct
24 Correct 7 ms 12380 KB Output is correct
25 Correct 10 ms 12304 KB Output is correct
26 Correct 8 ms 12380 KB Output is correct
27 Correct 7 ms 12376 KB Output is correct
28 Correct 8 ms 12380 KB Output is correct
29 Correct 8 ms 12216 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 9 ms 12376 KB Output is correct
20 Correct 7 ms 12376 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 8 ms 12380 KB Output is correct
23 Correct 7 ms 12124 KB Output is correct
24 Correct 7 ms 12380 KB Output is correct
25 Correct 10 ms 12304 KB Output is correct
26 Correct 8 ms 12380 KB Output is correct
27 Correct 7 ms 12376 KB Output is correct
28 Correct 8 ms 12380 KB Output is correct
29 Correct 8 ms 12216 KB Output is correct
30 Runtime error 703 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 9 ms 12376 KB Output is correct
20 Correct 7 ms 12376 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 8 ms 12380 KB Output is correct
23 Correct 7 ms 12124 KB Output is correct
24 Correct 7 ms 12380 KB Output is correct
25 Correct 10 ms 12304 KB Output is correct
26 Correct 8 ms 12380 KB Output is correct
27 Correct 7 ms 12376 KB Output is correct
28 Correct 8 ms 12380 KB Output is correct
29 Correct 8 ms 12216 KB Output is correct
30 Runtime error 703 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -