Submission #1045864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045864		Sputnik123	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define in insert
#define pll pair<ll,ll>
#define vpl vector<pll>
#define vll vector <ll>
#define vl vector<ll>
#define F first
#define ll long long
#define S second
#define all(v) v.begin(),v.end()
#define endl "\n"
#define ull unsigned long long
#define ld long double
using namespace std;
//using namespace __gnu_pbds;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
const ll sz=3e5+5;
const ll inf=1e18;
const ll mod=1e9+7;
const ll mod2=998244353;
const ll eps = 1e-12;
const ll P1=47; // for hashing 
const ll P2=41; // for hashing 
//template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// ll idx = 1;
long long count_swaps(vector<ll> s) {
    int n = s.size() / 2;
    if(n == 1)
    {
        if(s[0] < 0)    return 0;
                        return 1;
    }
    ll ans = 0;
    for(ll i = 0; i < n ;i++)
        ans += i;
    return ans;
}
void solve()
{
    ll n;
    string s;
    cin >> n >> s;
    string ans;
    map <char, ll> mp;
    for(char i : s)
        mp[i]++;
    ll t = 0;
    for(auto i : mp)
        t = max(t, i.S);
    if(t > ((n + 1)/ 2))
    {
        cout << "Impossible" << endl;
        return;
    }
    priority_queue <pair<ll, char>> pq;
    for(auto i : mp)
        pq.push({i.second, i.first});
    for(ll i = 0 ; i < s.size(); i++)
    {
        char res;
        if(pq.top().first != 0)
            res = pq.top().second;
        else
            res = '!';
        ll c = pq.top().first;
        pq.pop();
        if(c != 1)
        pq.push({c - 1, res});
        ans += res;
        mp[res]--;
    }
    // cout << ans << endl;
    for(ll i = 0; i < ans.size(); i++)
    {
        if(ans[i] == '!')
        {
            cout << "Impossible" << endl;
            return;
        }
    }
    map <char, vll> h;
    for(ll i = 0 ; i < n; i++)
        h[ans[i]].pb(i);
    vector <pair<char, ll>> sizes;
    for(auto i : h)
        sizes.push_back({i.first, i.second.size()});
    sort(all(sizes));
    for(ll i = 0; i < n; i++)
    {
        if(ans[i] == s[i])
        {
            for(ll j = 0; j < n; j++)
                if(ans[i] != ans[j] && ans[i] != s[j])
                {
                    swap(ans[i], ans[j]);
                    break;
                }
        }
    }
    // cout << ans << endl;
    for(ll i = 0; i < n; i++){
        if(ans[i] == s[i])
        {
            cout << "Impossible" << endl;
            return;
        }
    }
    cout << ans << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long t=1;
    // cin >> t;
    while(t--)
    {	   
        // cout << "Case " << (int) idx <<":\n";
        solve();
        ///idx++;
    }
}
/* 
Note : don`t use fast input in interactive questions
Note : Compare long double with eps = 1e-12
*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<long long int>)':
shoes.cpp:36:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   36 |         if(s[0] < 0)    return 0;
      |         ^~
shoes.cpp:37:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |                         return 1;
      |                         ^~~~~~
shoes.cpp: In function 'void solve()':
shoes.cpp:64:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(ll i = 0 ; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
shoes.cpp:79:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(ll i = 0; i < ans.size(); i++)
      |                   ~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/cc0Icuea.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2Tm4U7.o:shoes.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc0Icuea.o: in function `main':
grader.cpp:(.text.startup+0x2a8): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status