Submission #678025

#	Time	Username	Problem	Language	Result	Execution time	Memory
678025		DDDNNN	Ekoeko (COCI21_ekoeko)	C++14	0 / 110	5 ms	2632 KiB

Main

#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,1,n) cout<<a[i];
    forinc(i,1,2*n) pos[a[i]].push_back(i);
    forinc(i,0,26) reverse(pos[i].begin(),pos[i].end());

    forinc(i,1,2*n)
    {
        int val=s[i]-'a';
        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 (stderr)

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()
      | ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40