oj.uz

Submission #109394

# Submission time Handle Problem Language Result Execution time Memory
109394 2019-05-06T10:42:42 Z JustasZ Ancient Books (IOI17_books) C++14
22 / 100
 1349 ms 1049600 KB 
#include "books.h"
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 1e6 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, s, val[maxn], nxt, L[maxn], R[maxn];
vector<vector<int> > edge;
vector<int>p;
vector<pair<int, pii> > edges;
ll ans;
int par[maxn];
int root(int v)
{
    return v == par[v] ? v : par[v] = root(par[v]);
}
bool unite(int a, int b)
{
    a = root(a), b = root(b);
    if(a == b)
        return false;
    par[b] = a;
    return true;
}
void clr()
{
    for(int i = 0; i < maxn; i++)
    {
        L[i] = mod;
        R[i] = -mod;
    }
    ans = 0;
    nxt = 0;
    edges.clear();
    memset(val, 0, sizeof val);
}
ll minimum_walk(vector<int>perm, int S)
{
    clr();
    s = S;
    p = perm;
    n = sz(p);
    set<int>one;
    for(int i = 0; i < n; i++)
    {
        if(!val[i])
        {
            int col = ++nxt, cur = i, cnt = 0, chk = 0;
            while(!val[cur])
            {
                //cout << "-- " << cur << " " << col << endl;
                L[col] = min(L[col], cur);
                R[col] = max(R[col], cur);
                if(cur == s)
                    chk = 1;
                cnt++;
                val[cur] = col;
                ans += abs(p[cur] - cur);
                cur = p[cur];
            }
            if(cnt == 1 && !chk)
                one.insert(col);
        }
    }
    vector<int>belong[nxt + 1];
    for(int i = 0; i < n; i++)
        belong[val[i]].pb(i);
    edge = vector<vector<int> > (n, vector<int>(n, mod));
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(val[i] != val[j])
                edge[val[i]][val[j]] = min(edge[val[i]][val[j]], j - i);
        }
    }
    for(int i = 1; i <= nxt; i++)
    {
        //cout << i << " " << L[i] << " " << R[i] << endl;
        for(int j = 1; j <= nxt; j++)
        {
            if(i == j)
                continue;
            for(int a : belong[i])
            {
                for(int b : belong[j])
                {
                    if((a < b && p[a] > b) || (a > b && p[a] < b))
                        edge[i][j] = edge[j][i] = 0;
                }
                //if((a < L[j] && p[a] > R[j]) || (a > R[j] && p[a] < L[j]))
                    //edge[i][j] = edge[j][i] = 0;

            }
        }
    }
    for(int i = 1; i <= nxt; i++)
        par[i] = i;
    for(int i = 1; i <= nxt; i++)
        for(int j = i + 1; j <= nxt; j++)
            edges.pb({edge[i][j], {i, j}});
    sort(all(edges));
    for(auto aa : edges)
    {
        if(one.count(aa.y.x) || one.count(aa.y.y))
            continue;
        if(unite(aa.y.x, aa.y.y))
            ans += aa.x * 2;
    }
    return ans;
}
/*int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    vector<int>perm;
    for(int i = 0; i < 4; i++)
        perm.pb(i);
    do
    {
        for(int i = 0; i < 4; i++)
        {
            clr();
            cout << "permutaiton ";
            for(int a : perm)
                cout << a << " ";
            cout << endl;
            cout << "start: " << i << " " << minimum_walk(perm, i) << endl;
        }
    } while(next_permutation(all(perm)));
    ifstream fin("in.txt");
    int n, s;
    fin >> n >> s;
    perm.resize(n);
    for(int i = 0; i < n; i++)
        fin >> perm[i];
    cout << minimum_walk(perm, s) << endl;
    cout << minimum_walk({3, 2, 1, 0}, 0);
    return 0;
}*/

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12160 KB Output is correct
2 Correct 13 ms 12160 KB Output is correct
3 Correct 12 ms 12032 KB Output is correct
4 Correct 13 ms 12032 KB Output is correct
5 Correct 12 ms 12236 KB Output is correct
6 Correct 14 ms 12032 KB Output is correct
7 Correct 14 ms 12032 KB Output is correct
8 Correct 13 ms 12032 KB Output is correct
9 Correct 13 ms 12032 KB Output is correct
10 Correct 13 ms 12032 KB Output is correct
11 Correct 11 ms 12032 KB Output is correct
12 Correct 15 ms 12160 KB Output is correct
13 Correct 15 ms 12032 KB Output is correct
14 Correct 13 ms 12160 KB Output is correct
15 Correct 14 ms 12032 KB Output is correct
16 Correct 13 ms 12032 KB Output is correct
17 Correct 12 ms 12032 KB Output is correct
18 Correct 14 ms 12160 KB Output is correct
19 Correct 17 ms 16128 KB Output is correct
20 Correct 17 ms 16128 KB Output is correct
21 Correct 179 ms 22508 KB Output is correct
22 Correct 65 ms 19312 KB Output is correct
23 Correct 62 ms 19316 KB Output is correct
24 Correct 44 ms 17788 KB Output is correct
25 Correct 40 ms 17780 KB Output is correct
26 Correct 21 ms 16340 KB Output is correct
27 Correct 24 ms 16256 KB Output is correct
28 Correct 21 ms 16128 KB Output is correct
29 Correct 67 ms 19308 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12160 KB Output is correct
2 Correct 13 ms 12160 KB Output is correct
3 Correct 12 ms 12032 KB Output is correct
4 Correct 13 ms 12032 KB Output is correct
5 Correct 12 ms 12236 KB Output is correct
6 Correct 14 ms 12032 KB Output is correct
7 Correct 14 ms 12032 KB Output is correct
8 Correct 13 ms 12032 KB Output is correct
9 Correct 13 ms 12032 KB Output is correct
10 Correct 13 ms 12032 KB Output is correct
11 Correct 11 ms 12032 KB Output is correct
12 Correct 15 ms 12160 KB Output is correct
13 Correct 15 ms 12032 KB Output is correct
14 Correct 13 ms 12160 KB Output is correct
15 Correct 14 ms 12032 KB Output is correct
16 Correct 13 ms 12032 KB Output is correct
17 Correct 12 ms 12032 KB Output is correct
18 Correct 14 ms 12160 KB Output is correct
19 Correct 17 ms 16128 KB Output is correct
20 Correct 17 ms 16128 KB Output is correct
21 Correct 179 ms 22508 KB Output is correct
22 Correct 65 ms 19312 KB Output is correct
23 Correct 62 ms 19316 KB Output is correct
24 Correct 44 ms 17788 KB Output is correct
25 Correct 40 ms 17780 KB Output is correct
26 Correct 21 ms 16340 KB Output is correct
27 Correct 24 ms 16256 KB Output is correct
28 Correct 21 ms 16128 KB Output is correct
29 Correct 67 ms 19308 KB Output is correct
30 Runtime error 1349 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 19308 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 13 ms 12160 KB Output is correct
2 Correct 13 ms 12160 KB Output is correct
3 Correct 12 ms 12032 KB Output is correct
4 Correct 13 ms 12032 KB Output is correct
5 Correct 12 ms 12236 KB Output is correct
6 Correct 14 ms 12032 KB Output is correct
7 Correct 14 ms 12032 KB Output is correct
8 Correct 13 ms 12032 KB Output is correct
9 Correct 13 ms 12032 KB Output is correct
10 Correct 13 ms 12032 KB Output is correct
11 Correct 11 ms 12032 KB Output is correct
12 Correct 15 ms 12160 KB Output is correct
13 Correct 15 ms 12032 KB Output is correct
14 Correct 13 ms 12160 KB Output is correct
15 Correct 14 ms 12032 KB Output is correct
16 Correct 13 ms 12032 KB Output is correct
17 Correct 12 ms 12032 KB Output is correct
18 Correct 14 ms 12160 KB Output is correct
19 Correct 17 ms 16128 KB Output is correct
20 Correct 17 ms 16128 KB Output is correct
21 Correct 179 ms 22508 KB Output is correct
22 Correct 65 ms 19312 KB Output is correct
23 Correct 62 ms 19316 KB Output is correct
24 Correct 44 ms 17788 KB Output is correct
25 Correct 40 ms 17780 KB Output is correct
26 Correct 21 ms 16340 KB Output is correct
27 Correct 24 ms 16256 KB Output is correct
28 Correct 21 ms 16128 KB Output is correct
29 Correct 67 ms 19308 KB Output is correct
30 Runtime error 1349 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -