oj.uz

답안 #289277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
289277 2020-09-02T14:00:26 Z peti1234 고대 책들 (IOI17_books) C++17
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;
const int c=1000002;
bool v[c];
long long sum;
int n, t[c], kezd, veg, kis, nagy, bh, jh, mini[c], maxi[c], x[3], y[3];
vector<int> akt;
void dfs(int a) {
    if (v[a]) return;
    v[a]=true, akt.push_back(a);
    kis=min(kis, a), nagy=max(nagy, a);
    dfs(t[a]);
}
void le() {
    int pos=mini[kezd], d=kezd, db=0, v=maxi[kezd];
    while(bh<pos && v<=veg) {
        while(d>pos) {
            d--;
            pos=min(pos, mini[d]);
            v=max(v, maxi[d]);
        }
        if (bh<pos && v<=veg) {
            db++;
            pos--, pos=mini[pos], v=max(v, maxi[pos]);
        }
    }
    x[0]=db;
    if (v>veg) x[1]=pos, x[2]=v;
    else x[1]=-1;
}
void fel() {
    int pos=maxi[veg], d=veg, db=0, k=mini[kezd];
    while(kezd<=k && pos<jh) {
        while(d<pos) {
            d++;
            pos=max(pos, maxi[d]);
            k=min(k, mini[d]);
        }
        if (k<=kezd && pos<jh) {
            db++;
            pos++, pos=maxi[pos], k=min(k, mini[pos]);
        }
    }
    y[0]=db;
}
long long minimum_walk(vector<int> p, int s) {
    n=p.size(), kezd=s, veg=s, kis=s, nagy=s, bh, jh;
    for (int i=0; i<n; i++) {
        t[i]=p[i], sum+=(abs(p[i]-i));
        if (t[i]!=i) {
            if (bh==i) bh++;
            jh=i;
        }
        kis=n, nagy=0;
        dfs(i);
        for (int i=0; i<akt.size(); i++) mini[akt[i]]=kis, maxi[akt[i]]=nagy;
        akt.clear();
    }
    while(bh<kezd || veg<jh) {
        le(), fel();
        if (x[1]==-1) {
            sum+=2*(x[0]+y[0]);
            break;
        }
        sum+=2*min(x[0], y[0]);
        while(x[1]<kezd || veg<x[2]) {
            x[1]=min(x[1], mini[kezd]), x[2]=max(x[2], maxi[veg]);
            if (kezd>x[1]) kezd--;
            if (veg<x[2]) veg++;
        }
    }
    return sum;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:48:51: warning: right operand of comma operator has no effect [-Wunused-value]
   48 |     n=p.size(), kezd=s, veg=s, kis=s, nagy=s, bh, jh;
      |                                                   ^~
books.cpp:48:53: warning: right operand of comma operator has no effect [-Wunused-value]
   48 |     n=p.size(), kezd=s, veg=s, kis=s, nagy=s, bh, jh;
      |                                                     ^
books.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i=0; i<akt.size(); i++) mini[akt[i]]=kis, maxi[akt[i]]=nagy;
      |                       ~^~~~~~~~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB 3rd lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB 3rd lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB 3rd lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4150'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB 3rd lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -