oj.uz

Submission #283167

# Submission time Handle Problem Language Result Execution time Memory
283167 2020-08-25T10:48:24 Z Ruba_K Arranging Shoes (IOI19_shoes) C++14
10 / 100
 1000 ms 14276 KB 
#include "shoes.h"
#include<bits/stdc++.h>
using namespace std ;
vector<int > pos[200005];
vector<int>st ;
int idx ;
int binarysearch(int u){ sort(st.begin() , st.end());
    while(st.size() && st.back() > idx)st.pop_back();
    if(st.empty())return 0 ;

    if(st.back() < u)return 0 ;
    int l = 0 , r = st.size() , md ;
    while(l < r){
        md = (l + r) / 2 ;
        if(st[md] < u)l = md + 1 ;
        else r = md ;

    }
    return st.size() - l ;
}



long long count_swaps(vector<int> v) {
    int n = v.size() / 2 ;
    for(int i = 0 ; i < n * 2 ; i ++){
        pos[v[i] + n] .push_back(i) ;
    }
    long long ans = 0 ;

    for(int i = 2 * n - 1 ; i >= 0 ; i --){
        if(v[i] == 0)continue ;
        idx = i ;
        int p = v[i] * -1 + n ;
        pos[v[i] + n].pop_back();
        auto u = binarysearch(p);
        int sum = 0 ;


        v[pos[p].back()] = 0;
        sum = u ;
        sum = i - pos[p].back() - sum - 1 ;

        st.push_back(pos[p].back());
        pos[p].pop_back();

        sum += (v[i] < 0);


        ans += sum ;

    }


	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Incorrect 4 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Incorrect 4 ms 4992 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Execution timed out 1096 ms 14276 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Incorrect 4 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Incorrect 4 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -