結果
問題 | No.2804 Fixer And Ratism |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; // aをbで更新return true;}return false;}// aよりもbが小さいならばaをbで更新する// (更新されたならばtrueを返す)template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b; // aをbで更新return true;}return false;}ll floor(ll N, ll d){if(d < 0)N *= -1, d *= -1;if(N > 0)return N / d;elsereturn (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;elsereturn 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;}//aとmは互いに素, a^(-1) mod mlong 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 -> repairedunordered_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;}