oj.uz

Submission #917939

# Submission time Handle Problem Language Result Execution time Memory
917939 2024-01-29T06:31:39 Z nightfal Ancient Books (IOI17_books) C++14
42 / 100
 887 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;
}

long long cal(vector<int> p, int l, int r, int lmost, int rmost, vector<vector<long long>>& dp) {
    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(lmost,min(l-1,p[l-1])), 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]), rmostN = max(rmost,max(r+1,p[r+1]));
        temp2 += cal(p,l,r+1,lmostN,rmostN,dp); 
    }
    dp[l][r] = min(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;

    int l=s, r=s, lmost = min(s,p[s]), rmost = max(s,p[s]);
    return cal(p,l,r,lmost,rmost,dp)+abs(p[s]-s);
}

pair<int,int> extend(int l, int r, vector<int>& lmost, vector<int>& rmost) {
    while(l > min(lmost[l],lmost[r]) || r < max(rmost[l],rmost[r])) {
        l=min(l,min(lmost[l],lmost[r])); 
        r=max(r,max(rmost[r],rmost[l]));
    }
    return make_pair(l,r);
} 


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

    int n = p.size();

    // curtail ignorable head and tail.
    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); 
    // printf("s=%d, n=%d\n",s,n);

    int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
    long long totalMove=0, totalJump=0;
    for(int i=0; i<n; i++) totalJump += abs(p[i]-i);
    printf("totalJump=%d\n",totalJump);

    vector<int> lmost(n), rmost(n); 
    l = lmost[s] = min(s,p[s]), r = rmost[s] = max(s,p[s]);
    for(int i=s-1; i>=0; i--) {lmost[i] = min(lmost[i+1],p[i]); rmost[i] = max(rmost[i+1],p[i]);}
    for(int i=s+1; i<n ; i++) {lmost[i] = min(lmost[i-1],p[i]); rmost[i] = max(rmost[i-1],p[i]);}
    tie(l,r) = extend(l,r,lmost,rmost);

    while(0<l || r<n-1) {
        totalMove++; if(r<n-1) r++; if(l>0) l--;
        tie(l,r) = extend(l,r,lmost,rmost);
    }
 
    return totalMove*2+totalJump;
}

long long minimum_walk(std::vector<int> p, int s) {
    // if (isSubtask3(s)) return subtask3(p);
    if (isSubtask4(s)) return subtask4(p,s);
    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 'long long int fulltask(std::vector<int>, int)':
books.cpp:83:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   83 |     printf("totalJump=%d\n",totalJump);
      |                       ~^    ~~~~~~~~~
      |                        |    |
      |                        int  long long int
      |                       %lld
books.cpp:80:14: warning: unused variable 'lStart' [-Wunused-variable]
   80 |     int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
      |              ^~~~~~
books.cpp:80:29: warning: unused variable 'rStart' [-Wunused-variable]
   80 |     int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
      |                             ^~~~~~
books.cpp:80:39: warning: unused variable 'moveL' [-Wunused-variable]
   80 |     int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
      |                                       ^~~~~
books.cpp:80:48: warning: unused variable 'moveR' [-Wunused-variable]
   80 |     int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
      |                                                ^~~~~

Subtask #1
12.0 / 12.0

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

Subtask #3
0 / 28.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 12412 KB Output is correct
2 Correct 129 ms 12436 KB Output is correct
3 Correct 826 ms 12408 KB Output is correct
4 Correct 761 ms 12184 KB Output is correct
5 Correct 853 ms 12396 KB Output is correct
6 Correct 829 ms 12416 KB Output is correct
7 Correct 856 ms 12416 KB Output is correct
8 Correct 860 ms 12416 KB Output is correct
9 Correct 706 ms 12412 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 840 ms 12400 KB Output is correct
12 Correct 846 ms 12420 KB Output is correct
13 Correct 794 ms 12408 KB Output is correct
14 Correct 878 ms 12424 KB Output is correct
15 Correct 836 ms 12380 KB Output is correct
16 Correct 837 ms 12396 KB Output is correct
17 Correct 833 ms 12376 KB Output is correct
18 Correct 847 ms 12416 KB Output is correct
19 Correct 870 ms 12428 KB Output is correct
20 Correct 550 ms 12412 KB Output is correct

Subtask #5
0 / 30.0

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