Submission #53410380

Source Code Expand

// LUOGU_RID: 158818523
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mid ((l+r)>>1)
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=1e8;
// head
const int N=3e5+5;
vector<vector<int>> G(N);
int c[N],x[N];
int a[N],b[N];
int ans;
void msort(int l,int r,int op)
{
    if(l>=r) return ;
    msort(l,mid,op);msort(mid+1,r,op);
    int i=l,j=mid+1,now=l;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]) b[now++]=a[i++];
        else b[now++]=a[j++],ans+=(mid-i+1)*op;
    }
    while(i<=mid) b[now++]=a[i++];
    while(j<=r) b[now++]=a[j++];
    for(int x=l;x<=r;x++) a[x]=b[x];
}
signed main() 
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n;cin>>n;
    for(int i=0;i<n;i++) cin>>c[i];
    for(int i=0;i<n;i++) cin>>x[i];
    for(int i=0;i<n;i++) {G[c[i]].pb(x[i]);a[i]=x[i];}
    ans=0;
    msort(0,n-1,1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<G[i].size();j++) a[j]=G[i][j];
        msort(0,G[i].size()-1,-1);
    }
    cout<<ans<<endl;
}

Submission Info

Submission Time
Task F - Sorting Color Balls
User gangbengr
Language C++ 17 (gcc 12.2)
Score 500
Code Size 1235 Byte
Status AC
Exec Time 97 ms
Memory 28920 KiB

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:47:22: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   47 |         for(int j=0;j<G[i].size();j++) a[j]=G[i][j];
      |                     ~^~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 37
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt
Case Name Status Exec Time Memory
example_00.txt AC 4 ms 10036 KiB
example_01.txt AC 4 ms 10056 KiB
example_02.txt AC 4 ms 10092 KiB
hand_00.txt AC 70 ms 28920 KiB
hand_01.txt AC 77 ms 28836 KiB
hand_02.txt AC 69 ms 28920 KiB
hand_03.txt AC 48 ms 22116 KiB
hand_04.txt AC 63 ms 23092 KiB
hand_05.txt AC 4 ms 10124 KiB
hand_06.txt AC 4 ms 10092 KiB
random_00.txt AC 73 ms 24760 KiB
random_01.txt AC 81 ms 24380 KiB
random_02.txt AC 52 ms 23712 KiB
random_03.txt AC 51 ms 23016 KiB
random_04.txt AC 50 ms 22060 KiB
random_05.txt AC 81 ms 25000 KiB
random_06.txt AC 76 ms 23616 KiB
random_07.txt AC 66 ms 24152 KiB
random_08.txt AC 67 ms 22704 KiB
random_09.txt AC 65 ms 21796 KiB
random_10.txt AC 84 ms 24672 KiB
random_11.txt AC 87 ms 24504 KiB
random_12.txt AC 73 ms 23396 KiB
random_13.txt AC 76 ms 22836 KiB
random_14.txt AC 77 ms 22016 KiB
random_15.txt AC 87 ms 24700 KiB
random_16.txt AC 92 ms 24604 KiB
random_17.txt AC 76 ms 23712 KiB
random_18.txt AC 81 ms 23112 KiB
random_19.txt AC 86 ms 21832 KiB
random_20.txt AC 92 ms 24756 KiB
random_21.txt AC 93 ms 24432 KiB
random_22.txt AC 76 ms 23228 KiB
random_23.txt AC 79 ms 22868 KiB
random_24.txt AC 86 ms 22208 KiB
random_25.txt AC 97 ms 24992 KiB
random_26.txt AC 90 ms 24432 KiB