oj.uz

답안 #739992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739992 2023-05-11T19:46:20 Z nicolaev Arranging Shoes (IOI19_shoes) C++14
25 / 100
 1000 ms 21912 KB 
#include "shoes.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define mod                1000000007
#define ll                 int
#define all(v)             v.begin(), v.end()
#define fr(n)              for(ll i=0;i<n;++i)
#define ctz(x)             __builtin_ctzll(x)
#define clz(x)             __builtin_clzll(x)
#define pcount(x)          __builtin_popcountll(x)
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
// #define cin fin
// #define cout fout
// ifstream fin
// ofstream fout
//const ll maxn = 3e5 + 5;
//int f[maxn],nf[maxn],inv[maxn];
//const int M=998244353;
//void init(){
//inv[1]=1; for (int i=2;i<maxn;i++) inv[i]=M-1ll*(M/i)*inv[M%i]%M;
//f[0]=nf[0]=1; for (int i=1;i<maxn;i++) f[i]=1ll*f[i-1]*i%M,nf[i]=1ll*nf[i-1]*inv[i]%M;
//}
//int C(int x,int y){return 1ll*f[x]*nf[y]%M*nf[x-y]%M;}

long long count_swaps(vector<ll> s){
    ll n=s.size();
    vector< set<ll> > v(n+4);
    
    for(ll i=0; i<n; i++){
        if(s[i]<0){
            v[abs(s[i])+n/2].insert(i);
        }
        else v[s[i]].insert(i);
    }
    long long ans=0;
    ordered_set st;
    for(ll i=0; i<s.size(); i++){
        
        if(s[i]<0){
            if(v[abs(s[i])+n/2].empty()) continue;
            // set<ll> ::iterator it2=st.begin();
            // if(*it2<i) st.erase(st.begin());
            ll temp=st.order_of_key(i);
            

            v[abs(s[i])+n/2].erase(i);
            set<ll> ::iterator it=v[abs(s[i])].begin();
            ans+=*it-i-1;
            ans-=st.order_of_key(*it);
            ans+=temp;
            // ll temp=*it;
            // s.erase(s.begin() + temp);
            st.insert(*it);
            v[abs(s[i])].erase(it);
            
        }
        else{
            if(v[s[i]].empty()) continue;
            // ll temp=st.order_of_key(i);
            // if(temp){
            //     st.erase(st.begin(), st.begin()+temp);
            // }
            ll temp=st.order_of_key(i);
            v[s[i]].erase(i);
            set<ll> ::iterator it=v[n/2+s[i]].begin();
            ans+=*it-i;
            ans-=st.order_of_key(*it);
            ans+=temp;
            // s.erase(s.begin()+ (*it));
            st.insert(*it);
            v[n/2+s[i]].erase(it);
        }
        // cout<<ans;
    }
    return ans;
    
}

// int main(){
//     vector<ll> s;
//     ll n;cin>>n;
//     fr(n){
//         ll x;cin>>x;s.push_back(x);
//     }
//     cout<<count_swaps(s);
// }

Compilation message

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(ll i=0; i<s.size(); i++){
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Execution timed out 1081 ms 212 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Execution timed out 1068 ms 212 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 116 ms 21836 KB Output is correct
6 Correct 149 ms 21892 KB Output is correct
7 Correct 120 ms 21836 KB Output is correct
8 Correct 124 ms 21912 KB Output is correct
9 Correct 107 ms 21804 KB Output is correct
10 Correct 124 ms 21788 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Execution timed out 1081 ms 212 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Execution timed out 1081 ms 212 KB Time limit exceeded
18 Halted 0 ms 0 KB -