結果

問題 No.2804 Fixer And Ratism
ユーザー gyozasukisuki
提出日時 2024-07-12 23:37:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 44 ms / 2,000 ms
コード長 5,094 bytes
コンパイル時間 2,960 ms
コンパイル使用メモリ 221,112 KB
最終ジャッジ日時 2025-02-22 05:39:36
ジャッジサーバーID
(参考情報)
judge3 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/all>
// using namespace atcoder;
const int INF = 1e9;
using ll = long long;
using ull = unsigned long long;
using ullv = vector<ull>;
using inv = vector<int>;
using stv = vector<string>;
using llv = vector<ll>;
using ld = long double;
using pint = pair<int,int>;
#define FOR(i,l,r) for(int i=(int)(l); i<(int)(r); i++)
#define rep(i,r) for(ll i=0; i<(ll)(r); i++)
#define repl(i,r) for(long long i=0; i<(long long)(r); i++)
#define FORl(i,l,r) for(long long i=(long long)(l); i<(long long)(r); i++)
#define INFL (long long)((1LL<<62)-(1LL<<31))
#define pb(x) push_back(x)
#define printVec(x) for(auto s:x) cout << s << " "; cout << endl
#define ALL(x) x.begin(),x.end()
template <typename T>
bool chmax(T &a, const T& b) {
if (a < b) {
a = b; // ab
return true;
}
return false;
}
// abab
// (true)
template <typename T>
bool chmin(T &a, const T& b) {
if (a > b) {
a = b; // ab
return true;
}
return false;
}
ll floor(ll N, ll d){
if(d < 0)
N *= -1, d *= -1;
if(N > 0)
return N / d;
else
return (N+1) / d-1;
}
ll ceil(ll N, ll d)
{
if(d < 0)
N *= -1, d *= -1;
if(N > 0)
return (N - 1) / d + 1;
else
return N / d;
}
long long pow(long long x, long long n) {
long long ret = 1;
while (n > 0) {
if (n & 1) ret *= x; // n bit 1 x^(2^i)
x *= x;
n >>= 1; // n 1bit
}
return ret;
}
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
//
long long int ext_gcd(long long int a, long long int b, long long int &x, long long int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
long long int q = a / b;
long long int g = ext_gcd(b, a-q*b, x, y);
long long int z = x-q*y;
x = y;
y = z;
return g;
}
//am, a^(-1) mod m
long long int modinv(long long int a, long long int m)
{
long long int x, y;
ext_gcd(a, m, x, y);
x %= m;
if (x < 0)
x += m;
return x;
}
ll takemod(ll x,ll m){
ll num = x;
num %= m;
if (num < 0)
num += m;
return num;
}
const ll MOD = 998244353LL;
ll N;
string S,T;
ll convert(string s){
reverse(ALL(s));
ll res = 0;
rep(i,s.size()){
if(s[i] == 'B'){
res += (1LL << i);
}
}
return res;
}
string binary(ll bina){
string ans = "";
for (int i = 0; bina>0 ; i++)
{
if(bina%2) ans.pb('1');
else ans.pb('0');
bina = bina/2;
}
reverse(ALL(ans));
return ans;
}
string contos(ll n){
string ns = binary(n);
string ans = "";
for (int i = 0; n>0 ; i++)
{
if(n%2) ans.pb('B');
else ans.pb('W');
n= n/2;
}
rep(i,N-ns.size()+2) ans.pb('W');
reverse(ALL(ans));
return ans;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
// cout << fixed << setprecision(15);
ll N,Q;
cin >> N >> Q;
ll canuse = N;
set<pair<ll,string>> up,down; // up -> repaired
unordered_map<string,ll> mp;
while(Q--){
ll t;
cin >> t;
// cout << t << endl;
if(t == 1){
ll r;
string s;
cin >> s >> r;
// cout << s << " " << r << endl;
auto info = make_pair(r,s);
mp[s] = r;
down.insert(info);
// cout << info.second << " " << up.size() << " " << down.size() << endl;
if(up.size() + down.size() > canuse){
auto p = *down.begin();
down.erase(p);
cout << p.second << endl;
}
}else if(t == 2){
ll x;
cin >> x;
canuse -= x;
if(up.size() + down.size() > canuse){
vector<pair<ll,string>> u;
ll d= (up.size() +down.size())-canuse;
rep(i,d){
if(down.empty() && up.empty()) continue;
if(down.empty()){
auto p = *up.begin();
up.erase(p);
u.pb(p);
// cout << p.second << endl;
continue;
}
auto p = *down.begin();
down.erase(p);
u.pb(p);
// cout << p.second << endl;
}
sort(ALL(u));
rep(i,u.size()){
cout << u[i].second << endl;
}
}
}else if(t == 3){
ll x;
string s;
cin >> s >> x;
// cout << s << " " << x << endl;
auto info = make_pair(mp[s],s);
canuse += x;
if(up.find(info) == up.end()){
down.erase(info);
up.insert(info);
}
}
// cout << "...." << endl;
// for(auto [r,s] : down){
// cout << r << " " << s << endl;
// }
// cout << "----" << endl;
// for(auto [r,s] : up){
// cout << r << " " << s << endl;
// }
// cout << "...." << endl;
// cout << endl;
}
// cout << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0