Submission #678023

# Submission time Handle Problem Language Result Execution time Memory
678023 2023-01-05T03:21:29 Z DDDNNN Ekoeko (COCI21_ekoeko) C++14
0 / 110
4 ms 2636 KB
#include<bits/stdc++.h>
using namespace std;
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define fordec(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define getbit(x,i) ((x>>(i))&1ll)
#define batbit(x,i) (x|(1ll<<(i)))
#define tatbit(x,i) (x&~(1<<(i)))
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define fiora(i,v) for(auto &i:v)

int cnt[33],num[33];
int bit[200003];
int a[200002],b[200002];
vector<int> pos[33];
int n;
void upd(int i)
{
    for(i;i>0;i-=(i&-i)) bit[i]++;
}
int get(int i)
{
    int ans=0;
    for(i;i<=n+10;i+=(i&-i)) ans+=bit[i];
    return ans;
}
main()
{
    fast
    cin>>n;
    string s;
    cin>>s;
    s=('o') + s;
    forinc(i,1,2*n) cnt[s[i]-'a']++;
    vector<int> v1,v2;
    int it=0;
    forinc(i,1,2*n)
    {
        int val=s[i]-'a';
        pos[val].push_back(i);
        if(++num[val]<=cnt[val]/2) a[++it]=val;
    }

    forinc(i,n+1,2*n) a[i]=a[i-n];
    forinc(i,0,26) reverse(pos[i].begin(),pos[i].end());
    forinc(i,1,2*n)
    {
        int val=a[i];
        b[i]=pos[val].back();
        pos[val].pop_back();
    }

    int res=0;

    forinc(i,1,2*n)
    {
        //cout<<b[i]<<" ";
        res+=get(b[i]);
        upd(b[i]);
    }
    cout<<res;
}

Compilation message

Main.cpp: In function 'void upd(long long int)':
Main.cpp:22:9: warning: statement has no effect [-Wunused-value]
   22 |     for(i;i>0;i-=(i&-i)) bit[i]++;
      |         ^
Main.cpp: In function 'long long int get(long long int)':
Main.cpp:27:9: warning: statement has no effect [-Wunused-value]
   27 |     for(i;i<=n+10;i+=(i&-i)) ans+=bit[i];
      |         ^
Main.cpp: At global scope:
Main.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main()
      | ^~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 4 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 4 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 4 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 4 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -