답안 #42494 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42494	2018-02-27T18:17:31 Z	yusufake	고대 책들 (IOI17_books)	C++	42 / 100	169 ms	8428 KB

books

#include<bits/stdc++.h>
 
using namespace std;
 
#define _   int v, int tl, int tr, int l, int r
#define tm  (tl+tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r
 
#define mp make_pair
#define pb push_back
#define st first
#define nd second
 
typedef long long ll;
typedef pair < ll , ll > pp;
 
const int mod = 1e9 + 7;
const int N   = 1e3 + 3;
 
int W[N][N],H[N],T[N],n,i,j,l,r,t,x,a,b,mn,mx,ss,u;
int smn[N<<2],smx[N<<2];

void up(_){
   if(tl > r || tr < l) return;
   if(tl >= l && tr <= r) { smn[v] = min(smn[v] , a); smx[v] = max(smx[v] , b); return; }
   up(sol); up(sag); smn[v] = min(smn[v+v] , smn[v+v+1]);
   smx[v] = max(smx[v+v] , smx[v+v+1]);
}
void qry(_){
   if(tl > r || tr < l) return;
   if(tl >= l && tr <= r) { mn = min(mn,smn[v]); mx=max(mx,smx[v]); return; }
   qry(sol); qry(sag);
}


ll minimum_walk(vector < int > p, int s){
    x = 0;
    n = p.size();
    if(n > 1000) return 0;
    memset(smn , 22 , sizeof smn);
	for(i=0;i<n;i++){
		x += abs(p[i] - i);
		if(H[i]) continue;
		r = i;
		for(j=i; !H[j] ; j = p[j]){
			H[j] = 1;
			r = max(r , j);
		}
        for(j=i; !T[j] ; j = p[j]){
		    T[j] = 1;
            a = i;  b = r;
            up(1,0,n,j,j);
        }
    }
    
    for(i=0;i<n && p[i] == i; i++);
    for(j=n-1;j>=0 && p[j] == j; j--);

    priority_queue < pair < int , pp > > Q;
    Q.push(mp(0,mp(s,s))); ss = n;
    for(;Q.size();){
        l = Q.top().nd.st;
        r = Q.top().nd.nd;
        u = Q.top().st;
        Q.pop();
        if(W[l][r]) continue;
      //  cout << l << " " << r << " " << -u << " aa\n";
        if(l <= i && r >= j) ss = min(ss , -u);
        W[l][r] = 1;
        mn = n; mx = 0;
        qry(1,0,n,l,r);
        Q.push(mp(u,mp(mn,mx)));
        if(l) Q.push(mp(u-1,mp(l-1,r)));
        if(r < n-1) Q.push(mp(u-1,mp(l,r+1)));
    }
    
    return x + 2 * ss;
}	

//int main(){
  //  cout << minimum_walk({1,0,2,3} , 2);
//}

Compilation message

books.cpp: In function 'void up(int, int, int, int, int)':
books.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
books.cpp:7:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^
books.cpp:27:7: note: in expansion of macro 'sol'
    up(sol); up(sag); smn[v] = min(smn[v+v] , smn[v+v+1]);
       ^
books.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
books.cpp:8:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^
books.cpp:27:16: note: in expansion of macro 'sag'
    up(sol); up(sag); smn[v] = min(smn[v+v] , smn[v+v+1]);
                ^
books.cpp: In function 'void qry(int, int, int, int, int)':
books.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
books.cpp:7:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^
books.cpp:33:8: note: in expansion of macro 'sol'
    qry(sol); qry(sag);
        ^
books.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
books.cpp:8:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^
books.cpp:33:18: note: in expansion of macro 'sag'
    qry(sol); qry(sag);
                  ^

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	388 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	476 KB	Output is correct
6	Correct	1 ms	476 KB	Output is correct
7	Correct	1 ms	476 KB	Output is correct
8	Correct	1 ms	528 KB	Output is correct
9	Correct	1 ms	532 KB	Output is correct
10	Correct	1 ms	548 KB	Output is correct
11	Correct	1 ms	548 KB	Output is correct
12	Correct	1 ms	652 KB	Output is correct
13	Correct	1 ms	704 KB	Output is correct
14	Correct	1 ms	704 KB	Output is correct
15	Correct	1 ms	704 KB	Output is correct
16	Correct	1 ms	704 KB	Output is correct
17	Correct	1 ms	704 KB	Output is correct
18	Correct	1 ms	704 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	388 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	476 KB	Output is correct
6	Correct	1 ms	476 KB	Output is correct
7	Correct	1 ms	476 KB	Output is correct
8	Correct	1 ms	528 KB	Output is correct
9	Correct	1 ms	532 KB	Output is correct
10	Correct	1 ms	548 KB	Output is correct
11	Correct	1 ms	548 KB	Output is correct
12	Correct	1 ms	652 KB	Output is correct
13	Correct	1 ms	704 KB	Output is correct
14	Correct	1 ms	704 KB	Output is correct
15	Correct	1 ms	704 KB	Output is correct
16	Correct	1 ms	704 KB	Output is correct
17	Correct	1 ms	704 KB	Output is correct
18	Correct	1 ms	704 KB	Output is correct
19	Correct	2 ms	704 KB	Output is correct
20	Correct	2 ms	704 KB	Output is correct
21	Correct	2 ms	704 KB	Output is correct
22	Correct	2 ms	704 KB	Output is correct
23	Correct	2 ms	704 KB	Output is correct
24	Correct	2 ms	704 KB	Output is correct
25	Correct	3 ms	704 KB	Output is correct
26	Correct	2 ms	704 KB	Output is correct
27	Correct	2 ms	704 KB	Output is correct
28	Correct	2 ms	704 KB	Output is correct
29	Correct	2 ms	704 KB	Output is correct

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	388 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	476 KB	Output is correct
6	Correct	1 ms	476 KB	Output is correct
7	Correct	1 ms	476 KB	Output is correct
8	Correct	1 ms	528 KB	Output is correct
9	Correct	1 ms	532 KB	Output is correct
10	Correct	1 ms	548 KB	Output is correct
11	Correct	1 ms	548 KB	Output is correct
12	Correct	1 ms	652 KB	Output is correct
13	Correct	1 ms	704 KB	Output is correct
14	Correct	1 ms	704 KB	Output is correct
15	Correct	1 ms	704 KB	Output is correct
16	Correct	1 ms	704 KB	Output is correct
17	Correct	1 ms	704 KB	Output is correct
18	Correct	1 ms	704 KB	Output is correct
19	Correct	2 ms	704 KB	Output is correct
20	Correct	2 ms	704 KB	Output is correct
21	Correct	2 ms	704 KB	Output is correct
22	Correct	2 ms	704 KB	Output is correct
23	Correct	2 ms	704 KB	Output is correct
24	Correct	2 ms	704 KB	Output is correct
25	Correct	3 ms	704 KB	Output is correct
26	Correct	2 ms	704 KB	Output is correct
27	Correct	2 ms	704 KB	Output is correct
28	Correct	2 ms	704 KB	Output is correct
29	Correct	2 ms	704 KB	Output is correct
30	Incorrect	169 ms	8428 KB	3rd lines differ - on the 1st token, expected: '333035179244', found: '0'
31	Halted	0 ms	0 KB	-

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	146 ms	8428 KB	Output is correct
2	Correct	21 ms	8428 KB	Output is correct
3	Correct	151 ms	8428 KB	Output is correct
4	Correct	147 ms	8428 KB	Output is correct
5	Correct	151 ms	8428 KB	Output is correct
6	Correct	132 ms	8428 KB	Output is correct
7	Correct	144 ms	8428 KB	Output is correct
8	Correct	152 ms	8428 KB	Output is correct
9	Correct	141 ms	8428 KB	Output is correct
10	Correct	5 ms	8428 KB	Output is correct
11	Correct	146 ms	8428 KB	Output is correct
12	Correct	147 ms	8428 KB	Output is correct
13	Correct	149 ms	8428 KB	Output is correct
14	Correct	166 ms	8428 KB	Output is correct
15	Correct	153 ms	8428 KB	Output is correct
16	Correct	147 ms	8428 KB	Output is correct
17	Correct	159 ms	8428 KB	Output is correct
18	Correct	159 ms	8428 KB	Output is correct
19	Correct	160 ms	8428 KB	Output is correct
20	Correct	103 ms	8428 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	388 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	476 KB	Output is correct
6	Correct	1 ms	476 KB	Output is correct
7	Correct	1 ms	476 KB	Output is correct
8	Correct	1 ms	528 KB	Output is correct
9	Correct	1 ms	532 KB	Output is correct
10	Correct	1 ms	548 KB	Output is correct
11	Correct	1 ms	548 KB	Output is correct
12	Correct	1 ms	652 KB	Output is correct
13	Correct	1 ms	704 KB	Output is correct
14	Correct	1 ms	704 KB	Output is correct
15	Correct	1 ms	704 KB	Output is correct
16	Correct	1 ms	704 KB	Output is correct
17	Correct	1 ms	704 KB	Output is correct
18	Correct	1 ms	704 KB	Output is correct
19	Correct	2 ms	704 KB	Output is correct
20	Correct	2 ms	704 KB	Output is correct
21	Correct	2 ms	704 KB	Output is correct
22	Correct	2 ms	704 KB	Output is correct
23	Correct	2 ms	704 KB	Output is correct
24	Correct	2 ms	704 KB	Output is correct
25	Correct	3 ms	704 KB	Output is correct
26	Correct	2 ms	704 KB	Output is correct
27	Correct	2 ms	704 KB	Output is correct
28	Correct	2 ms	704 KB	Output is correct
29	Correct	2 ms	704 KB	Output is correct
30	Incorrect	169 ms	8428 KB	3rd lines differ - on the 1st token, expected: '333035179244', found: '0'
31	Halted	0 ms	0 KB	-

답안 #42494

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
0 / 30.0