1623-C

Problem - C - Codeforces

 

풀이

※ 결과가 최소가 되게하는 최대 ~, 결과가 최대가 되게하는 최소 ~ 가 나오면 parametric search 고려해보자

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> p(n);
        for(auto& e: p) cin >> e;
        string pre;
        cin >> pre;
 
        priority_queue<pi, vector<pi>, greater<> > pq_dislike;
        priority_queue<pi, vector<pi>, greater<> > pq_like;
 
        ooop(i, n){
            if(pre[i] == '0') pq_dislike.push({p[i], i});
            else pq_like.push({p[i], i});
        }
 
        vector<int> res(n);
        int ord = 1;
        while(!pq_dislike.empty()){
            auto [_, ind] = pq_dislike.top(); pq_dislike.pop();
            res[ind] = ord;
            ord++;
        }
        while(!pq_like.empty()){
            auto [_, ind] = pq_like.top(); pq_like.pop();
            res[ind] = ord;
            ord++;
        }
 
        for(auto e: res) cout << e << ' ';
        cout << endl;
 
 
 
    }
 
    return 0;
}cs