oj.uz

답안 #275904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
275904 2020-08-20T08:19:50 Z khangal Arranging Shoes (IOI19_shoes) C++14
10 / 100
 139 ms 45676 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define po pop_back
#define pb push_back
#define mk make_pair
#define mt make_tuple
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define BOOST ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18
#define MIN -1e18
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
#define read(x) scanf("%lld",&x);
#define print(x) printf("%lld ",x);
#define endl '\n';
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,ans,mid,mn,mx,cnt,T,sum,h1,h2,e[1234567],b[1234567],c[1234567],d[1<<20],k,i,j,l,r,h,a[1234567],w,x,y,z;
bool used[1234567];
vector<int> v[1234567],vec,vv1,vv2;
string s1,s;
int sz[1234567],par[1234567];
int tr[1234567];
ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123];
map<int,vector<int>> mp,mp1;
void Add(ll x, ll val){
    while(x <= 2 * n){
        tr[x] += val;
        x += (x&-x);
    }
}
ll Sum(ll x){
    ll res = 0;
    while(x){
        res +=tr[x];
        x -= (x&-x);
    }
    return res;
}
int count_swaps(vector<int> vec){
    vl A[123456],B[123456];
    n=vec.size()/2;
    rep(i,0,vec.size()-1){
        if(vec[i]<0)A[vec[i]*-1].pb(i);
        else B[vec[i]].pb(i);
    }
    vector<pair<int,int>>vpl;
    rep(i,1,n){
        for(ll j=0;j<A[i].size();j++){
            x = A[i][j];
            y = B[i][j];
            if(x>y){
                ans++;
                swap(x,y);
            }
            vpl.pb({x,y});
        }
    }
    sort(vpl.begin(),vpl.end());
    for(auto u:vpl){
        x=u.ff;
        y=u.ss;
        ans+=(Sum(y)-Sum(x))+2*(Sum(n)-Sum(y));
        Add(y,1);
    }
    return ans; 
}

Compilation message

shoes.cpp: In function 'int count_swaps(std::vector<int>)':
shoes.cpp:23:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define rep(i,a,b) for(ll i=a;i<=b;i++)
......
   59 |     rep(i,0,vec.size()-1){
      |         ~~~~~~~~~~~~~~~~        
shoes.cpp:59:5: note: in expansion of macro 'rep'
   59 |     rep(i,0,vec.size()-1){
      |     ^~~
shoes.cpp:65:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(ll j=0;j<A[i].size();j++){
      |                    ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 35072 KB Output is correct
2 Correct 32 ms 35072 KB Output is correct
3 Incorrect 25 ms 35064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 35072 KB Output is correct
2 Correct 32 ms 35072 KB Output is correct
3 Correct 30 ms 35072 KB Output is correct
4 Correct 27 ms 35200 KB Output is correct
5 Correct 42 ms 35064 KB Output is correct
6 Correct 25 ms 35072 KB Output is correct
7 Correct 27 ms 35064 KB Output is correct
8 Correct 39 ms 35064 KB Output is correct
9 Correct 33 ms 35200 KB Output is correct
10 Correct 33 ms 35064 KB Output is correct
11 Correct 25 ms 35072 KB Output is correct
12 Correct 25 ms 35072 KB Output is correct
13 Incorrect 30 ms 35072 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 35072 KB Output is correct
2 Correct 24 ms 35072 KB Output is correct
3 Correct 30 ms 35072 KB Output is correct
4 Correct 25 ms 35072 KB Output is correct
5 Incorrect 139 ms 45676 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 35072 KB Output is correct
2 Correct 32 ms 35072 KB Output is correct
3 Incorrect 25 ms 35064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 35072 KB Output is correct
2 Correct 32 ms 35072 KB Output is correct
3 Incorrect 25 ms 35064 KB Output isn't correct
4 Halted 0 ms 0 KB -