tctl/runway.cpp at master · miro-balaz/tctl · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include<algorithm>
#include <iomanip>
#include<stack>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

using namespace std;

void solve_case()
{
    int n,m;
    cin>>n>>m;
    vector<int> s(m);
    vector<int> has(m,1);
    REP(i,m) cin>>s[i];
    int rval=0;
    int X=10000000;
    REP(j,n) {
        vector<int> p(m+1);
        REP(i,m) cin>>p[i];
        p[m]=1000000002;
        sort(p.begin(), p.end());
        vector<pair<int, int> > v(m+1);
        REP(i,m) v[i]=make_pair(s[i],i+has[i]*X);
        v[m]=make_pair(1000000001,0);
        sort(v.begin(), v.end());
        stack<int> o,t;


        int xp=0, xv=0;

        while(xp<m || xv<m) {
            if(p[xp]==v[xv].first) {
                ++xp;
                ++xv;
            } else if(p[xp]<v[xv].first) {
                o.push(p[xp]);
                ++xp;
            } else {
                t.push(v[xv].second);
                ++xv;
            }

        }
        while(!o.empty()) {
            int sa=o.top();
            int sb=t.top();
            if(sb>=X)sb-=X;
            o.pop();
            t.pop();
            s[sb]=sa;
            if(has[sb]) {
                has[sb]=0;
            } else {
                ++rval;
            }

        }
        // REP(i,m) {
        //     cout<<s[i];
        //     if(has[i]) cout<<"*";
        //     cout<< " ";
        // }
        // cout<<endl;


    }
    cout<<rval<<endl;
}
int main()
{
        std::ios::sync_with_stdio(false);
        // y	our code goes here
        int T;
        cin >> T;
        REP(i, T) {
            cout<<"Case #"<<(i+1)<<": ";
            solve_case();
        }
        return 0;
}