oj.uz

Submission #422839

# Submission time Handle Problem Language Result Execution time Memory
422839 2021-06-10T12:59:18 Z 2fat2code Ancient Books (IOI17_books) C++17
0 / 100
 18 ms 23908 KB 
#include "books.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 1000005;

long long n, ans = 0, viz[nmax], comp = 0, cost, diff = 1e18, el = 0;
vector<pair<long long,long long>>ranges;
vector<long long>nod[nmax];

long long minimum_walk(vector<int> p, int s) {
	n = (int)p.size();
	for(int i=0;i<n;i++){
        ans += abs(p[i] - i);
	}
	for(int i=s;i>=0;i--){
        if(p[i] != i){
            if(abs(s-i) < diff){
                diff = abs(i - s);
                el = i;
            }
        }
	}
	for(int i=s;i<n;i++){
        if(p[i] != i){
            if(abs(s-i) < diff){
                diff = abs(i - s);
                el = i;
            }
        }
	}
	s = el;
	//cout << s << '\n';
	for(int i=0;i<n;i++){
        if(!viz[i]){
            int maxi = i, mini = i;
            comp++;
            viz[i] = comp;
            int curr = p[i];
            while(curr != i){
                viz[curr] = comp;
                maxi = max(maxi, curr);
                mini = min(mini, curr);
                curr = p[curr];
            }
            ranges.push_back({mini, maxi});
        }
	}
    while(ranges.size() && ranges.back().fr == ranges.back().sc && ranges.back().sc > s){
        ranges.pop_back();
    }
    reverse(all(ranges));
    while(ranges.size() && ranges.back().fr == ranges.back().sc && ranges.back().sc < s){
        ranges.pop_back();
    }
	sort(all(ranges));
	deque<pair<int,int>>Q;
	for(auto it : ranges){
        Q.push_back(it);
	}
	queue<pair<long long, long long>>rn;
	while(Q.size()){
        cost += 2;
        rn.push(Q.front());
        Q.pop_front();
        while(rn.size()){
            auto it = rn.front();
            rn.pop();
            while(Q.size() && Q.front().fr <= it.sc){
                rn.push(Q.front());
                Q.pop_front();
            }
        }
	}
	cost -= 2LL;
	return ans + cost + diff * 2LL;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23744 KB Output is correct
2 Correct 15 ms 23672 KB Output is correct
3 Correct 16 ms 23736 KB Output is correct
4 Correct 16 ms 23780 KB Output is correct
5 Correct 16 ms 23776 KB Output is correct
6 Correct 18 ms 23908 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 16 ms 23776 KB Output is correct
9 Incorrect 17 ms 23756 KB 3rd lines differ - on the 1st token, expected: '0', found: '2000000000000000000'
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23744 KB Output is correct
2 Correct 15 ms 23672 KB Output is correct
3 Correct 16 ms 23736 KB Output is correct
4 Correct 16 ms 23780 KB Output is correct
5 Correct 16 ms 23776 KB Output is correct
6 Correct 18 ms 23908 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 16 ms 23776 KB Output is correct
9 Incorrect 17 ms 23756 KB 3rd lines differ - on the 1st token, expected: '0', found: '2000000000000000000'
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23744 KB Output is correct
2 Correct 15 ms 23672 KB Output is correct
3 Correct 16 ms 23736 KB Output is correct
4 Correct 16 ms 23780 KB Output is correct
5 Correct 16 ms 23776 KB Output is correct
6 Correct 18 ms 23908 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 16 ms 23776 KB Output is correct
9 Incorrect 17 ms 23756 KB 3rd lines differ - on the 1st token, expected: '0', found: '2000000000000000000'
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23744 KB Output is correct
2 Correct 15 ms 23672 KB Output is correct
3 Correct 16 ms 23736 KB Output is correct
4 Correct 16 ms 23780 KB Output is correct
5 Correct 16 ms 23776 KB Output is correct
6 Correct 18 ms 23908 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 16 ms 23776 KB Output is correct
9 Incorrect 17 ms 23756 KB 3rd lines differ - on the 1st token, expected: '0', found: '2000000000000000000'
10 Halted 0 ms 0 KB -