結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー tactac
提出日時 2019-06-21 22:20:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 45 ms / 1,000 ms
コード長 4,597 bytes
コンパイル時間 2,159 ms
コンパイル使用メモリ 176,808 KB
実行使用メモリ 5,732 KB
最終ジャッジ日時 2024-06-07 16:55:51
合計ジャッジ時間 3,887 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
5,248 KB
testcase_01 AC 27 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 42 ms
5,732 KB
testcase_13 AC 43 ms
5,472 KB
testcase_14 AC 42 ms
5,600 KB
testcase_15 AC 45 ms
5,600 KB
testcase_16 AC 41 ms
5,456 KB
testcase_17 AC 41 ms
5,460 KB
testcase_18 AC 41 ms
5,456 KB
testcase_19 AC 42 ms
5,596 KB
testcase_20 AC 41 ms
5,596 KB
testcase_21 AC 43 ms
5,452 KB
testcase_22 AC 27 ms
5,488 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
/*
 #include<iostream>
 #include<vector>
 #include<algorithm>
 #include<cmath>
 */
using namespace std;
//type
typedef long long ll;
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<ll>
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define eps 1e-10
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
//manip
template<class T> bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, T b) {if (a > b) {a = b; return 1;} return 0;}
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end())
#define fill(x, y) memset(x, y, sizeof(x))
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power(T a, T b)
{return b ? power(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
//output
#define out(a) cout << a << endl
#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl
#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl;
#define outp(v) rep(i, SZ(v)) cout << v[i].F << " " << v[i].S << endl
#define outc(s, t) cout << fixed << setprecision(10) << (double)(t - s) / CLOCKS_PER_SEC << endl
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep3(i, st, n) for (int i = st; i < n; ++i)
#define rrep(i, n) for (int i = n; i >= 0; --i)
//algorithm (have library)
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0, while r < n





bool comp(pair<int, pii> a, pair<int, pii> b) {
    //if (a.S.F != b.S.F) return a.S.F > b.S.F;
    //return a.S.S > b.S.S;
    return a.S.F > b.S.F;
}
bool comp2(pair<int, pii> a, pair<int, pii> b) {
    //if (a.S.F != b.S.F) return a.S.F > b.S.F;
    //return a.S.S > b.S.S;
    return a.S.S < b.S.S;
}
int main() {
    //cast caution
    //look constraints always
    cin.tie(0); ios::sync_with_stdio(false);
    
    
    
    
    
    int n, m; cin >> n >> m;
    int c = 0;
    vector<pair<int, pii> > v;
    int acm3 = 0, acm2 = 0; //ac more than or equal to
    int x[n]; fill_n(x, n, 0);
    rep(i, n) {
        int a, b; cin >> x[i] >> a >> b;
        x[i]++; //a全員解けてる状態
        if (x[i] - 1 != 3) v.eb(i, pii(a, b));
        else {
            //n--;
            c++;
        }
        if (x[i] >= 3) acm3++;
        if (x[i] >= 2) acm2++;
    }
    //n -= c;
    if (c >= m) { //入力の時点で3以上の
        //cout << "c ";
        cout << c << endl;
        return 0;
    }
    sort(all(v), comp);
    vector<pair<int, pii> > v2 = v;
    sort(all(v2), comp2);
    int ans = inf;
    if (acm2 >= m) ans = acm3;
    rep(sa, 100002) {
        int flg = 0;
        while (SZ(v) && v[v.size() - 1].S.F == sa - 1) { //手前の人が解けない
            x[v[v.size() - 1].F]--;
            if (x[v[v.size() - 1].F] == 2) acm3--;
            else if (x[v[v.size() - 1].F] == 1) acm2--;
            v.erase(v.end() - 1);
        }
        if (acm2 >= m) {
            chmin(ans, acm3);
            if (SZ(v)) continue;
            else flg++;
        }
        for (int sb = v2[SZ(v2) - 1].S.S; sb >= 0; --sb) {
            if (SZ(v2) <= 0) {flg++; break;}
            while (v2[SZ(v2) - 1].S.S == sb) {
                x[v2[SZ(v2) - 1].F]++;
                if (x[v2[SZ(v2) - 1].F] == 2) acm2++;
                if (x[v2[SZ(v2) - 1].F] == 3) acm3++;
                v2.erase(v2.end() - 1);
                if (SZ(v2) <= 0) {flg++; break;}
            }
            if (flg) break;
            if (acm2 >= m) break;
        }
        if (flg == 2) break;
        if (acm2 >= m) {
            chmin(ans, acm3);
        }
        if (!SZ(v)) break;
    }
    //cout << "ans ";
    cout << ans << endl;
    
    
    
    
    
}
//cast caution



/*
 目的は2つ
 1. 2完以上をm人以上
 2. 3完以上を最小化
 
 1. の上で2. を目指す
 
 「2完以上m人付近」を全探索すれば答が求まる
 
 毎回操作が一意になるようにしたい
 
 最初
 a 0, b infにする
 
 2完以上m人以上ならa厳しく
 m人未満ならbやさしく
 と、一意に決まる
 
 
 a 0, b inf
 最初m人付近ではないこともある
 m人付近まで
 なんかたどる
 
 あとはm人付近をうろうろ
 
 a inf, b 0でも
 逆の経路みたいになる
 m人付近では同じ
 
 
 */
0