| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 887924 | 2023-12-15T13:44:40 Z | thunopro | Arranging Shoes (IOI19_shoes) | C++14 | 29 ms | 12624 KB |
#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009
#define ll long long
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
const int mod = 1e9+7 ;
const int INF = 1e9 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
typedef pair<ll,ll> pll ;
void add ( int &a , int b )
{
a += b ;
if ( a < 0 ) a += mod ;
if ( a >= mod ) a -= mod ;
}
template < typename T > void chkmin (int &a , int b) { if (a>b) a=b ;}
template < typename T > void chkmax (int &a , int b) { if (a<b) a=b ;}
void rf ()
{
freopen ("bai1.inp","r",stdin) ;
// freopen ("bai1.out","w",stdout) ;
}
int n ;
int a [maxn] ;
vi shoes [maxn] ;
int bit [maxn] ;
void update ( int x )
{
while ( x ) bit [x] ++ , x -= (x&-x) ;
}
int get ( int x )
{
int res = 0 ;
while ( x < maxn ) res += bit [x] , x += (x&-x) ;
return res ;
}
ll count_swaps ( vi _a )
{
n = _a.size () ;
for ( int i = 1 ; i <= n ; i ++ ) a [i] = _a [i-1] ;
for ( int i = n ; i >= 1 ; i -- ) if ( a [i] > 0 ) shoes [a[i]] . pb (i) ;
ll res = 0 ;
int cur = 1 ;
for ( int i = 1 ; i <= n ; i ++ )
{
if ( a [i] < 0 )
{
res += get (i) + i - cur ; cur ++ ;
update (i) ;
int pos = shoes[-a[i]].back () ; shoes[-a[i]].pop_back () ;
res += get (pos) + pos - cur ; cur ++ ;
update (pos) ;
}
}
return res ;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5724 KB | Output is correct |
| 2 | Correct | 1 ms | 5724 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5724 KB | Output is correct |
| 2 | Correct | 1 ms | 5724 KB | Output is correct |
| 3 | Correct | 1 ms | 5724 KB | Output is correct |
| 4 | Correct | 1 ms | 5724 KB | Output is correct |
| 5 | Correct | 1 ms | 5724 KB | Output is correct |
| 6 | Correct | 1 ms | 5560 KB | Output is correct |
| 7 | Correct | 1 ms | 5720 KB | Output is correct |
| 8 | Correct | 1 ms | 5724 KB | Output is correct |
| 9 | Correct | 1 ms | 5724 KB | Output is correct |
| 10 | Correct | 1 ms | 5724 KB | Output is correct |
| 11 | Correct | 1 ms | 5724 KB | Output is correct |
| 12 | Correct | 1 ms | 5724 KB | Output is correct |
| 13 | Correct | 2 ms | 5724 KB | Output is correct |
| 14 | Incorrect | 2 ms | 5724 KB | Output isn't correct |
| 15 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5724 KB | Output is correct |
| 2 | Correct | 1 ms | 5724 KB | Output is correct |
| 3 | Correct | 2 ms | 5880 KB | Output is correct |
| 4 | Correct | 1 ms | 5724 KB | Output is correct |
| 5 | Correct | 2 ms | 5720 KB | Output is correct |
| 6 | Correct | 2 ms | 5724 KB | Output is correct |
| 7 | Correct | 3 ms | 5616 KB | Output is correct |
| 8 | Correct | 1 ms | 5724 KB | Output is correct |
| 9 | Correct | 1 ms | 5724 KB | Output is correct |
| 10 | Correct | 1 ms | 5724 KB | Output is correct |
| 11 | Correct | 2 ms | 5724 KB | Output is correct |
| 12 | Correct | 1 ms | 5724 KB | Output is correct |
| 13 | Correct | 1 ms | 5724 KB | Output is correct |
| 14 | Correct | 1 ms | 5724 KB | Output is correct |
| 15 | Correct | 1 ms | 5724 KB | Output is correct |
| 16 | Correct | 1 ms | 5724 KB | Output is correct |
| 17 | Correct | 1 ms | 5724 KB | Output is correct |
| 18 | Correct | 2 ms | 5724 KB | Output is correct |
| 19 | Correct | 2 ms | 5724 KB | Output is correct |
| 20 | Correct | 4 ms | 5976 KB | Output is correct |
| 21 | Correct | 4 ms | 5976 KB | Output is correct |
| 22 | Correct | 24 ms | 8708 KB | Output is correct |
| 23 | Correct | 19 ms | 8664 KB | Output is correct |
| 24 | Correct | 27 ms | 8664 KB | Output is correct |
| 25 | Correct | 21 ms | 8660 KB | Output is correct |
| 26 | Correct | 24 ms | 9836 KB | Output is correct |
| 27 | Correct | 19 ms | 9724 KB | Output is correct |
| 28 | Correct | 22 ms | 9932 KB | Output is correct |
| 29 | Correct | 22 ms | 9932 KB | Output is correct |
| 30 | Correct | 21 ms | 9944 KB | Output is correct |
| 31 | Correct | 24 ms | 9984 KB | Output is correct |
| 32 | Correct | 21 ms | 9940 KB | Output is correct |
| 33 | Correct | 22 ms | 9712 KB | Output is correct |
| 34 | Correct | 21 ms | 9940 KB | Output is correct |
| 35 | Correct | 2 ms | 5724 KB | Output is correct |
| 36 | Correct | 1 ms | 5724 KB | Output is correct |
| 37 | Correct | 23 ms | 9844 KB | Output is correct |
| 38 | Correct | 22 ms | 9936 KB | Output is correct |
| 39 | Correct | 21 ms | 9944 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5724 KB | Output is correct |
| 2 | Correct | 1 ms | 5724 KB | Output is correct |
| 3 | Correct | 1 ms | 5724 KB | Output is correct |
| 4 | Correct | 1 ms | 5720 KB | Output is correct |
| 5 | Correct | 29 ms | 11144 KB | Output is correct |
| 6 | Correct | 29 ms | 10336 KB | Output is correct |
| 7 | Correct | 29 ms | 12624 KB | Output is correct |
| 8 | Correct | 22 ms | 9928 KB | Output is correct |
| 9 | Correct | 26 ms | 12624 KB | Output is correct |
| 10 | Correct | 27 ms | 11096 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5724 KB | Output is correct |
| 2 | Correct | 1 ms | 5724 KB | Output is correct |
| 3 | Correct | 1 ms | 5724 KB | Output is correct |
| 4 | Correct | 1 ms | 5724 KB | Output is correct |
| 5 | Correct | 1 ms | 5724 KB | Output is correct |
| 6 | Correct | 1 ms | 5560 KB | Output is correct |
| 7 | Correct | 1 ms | 5720 KB | Output is correct |
| 8 | Correct | 1 ms | 5724 KB | Output is correct |
| 9 | Correct | 1 ms | 5724 KB | Output is correct |
| 10 | Correct | 1 ms | 5724 KB | Output is correct |
| 11 | Correct | 1 ms | 5724 KB | Output is correct |
| 12 | Correct | 1 ms | 5724 KB | Output is correct |
| 13 | Correct | 2 ms | 5724 KB | Output is correct |
| 14 | Incorrect | 2 ms | 5724 KB | Output isn't correct |
| 15 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5724 KB | Output is correct |
| 2 | Correct | 1 ms | 5724 KB | Output is correct |
| 3 | Correct | 1 ms | 5724 KB | Output is correct |
| 4 | Correct | 1 ms | 5724 KB | Output is correct |
| 5 | Correct | 1 ms | 5724 KB | Output is correct |
| 6 | Correct | 1 ms | 5560 KB | Output is correct |
| 7 | Correct | 1 ms | 5720 KB | Output is correct |
| 8 | Correct | 1 ms | 5724 KB | Output is correct |
| 9 | Correct | 1 ms | 5724 KB | Output is correct |
| 10 | Correct | 1 ms | 5724 KB | Output is correct |
| 11 | Correct | 1 ms | 5724 KB | Output is correct |
| 12 | Correct | 1 ms | 5724 KB | Output is correct |
| 13 | Correct | 2 ms | 5724 KB | Output is correct |
| 14 | Incorrect | 2 ms | 5724 KB | Output isn't correct |
| 15 | Halted | 0 ms | 0 KB | - |