-
Notifications
You must be signed in to change notification settings - Fork 0
/
line.cpp
126 lines (115 loc) · 3.41 KB
/
line.cpp
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <queue>
#include "string.h"
using namespace std;
int comp_len;
int app_len;
int on_match_num;
int on_done_num;
bool on_match[26];
bool on_done[26];
vector<int> priority[26];
int max_prior[26];
int max_need[26];
bool cur_app[26][26];
queue<int> need[26];
vector<string> solution(vector<string> companies, vector<string> applicants) {
comp_len = companies.size();
app_len = applicants.size();
for(int i=0; i<companies.size(); i++) {
int here = 0;
for(int j=0; j<companies[i].size(); j++) {
if(companies[i][j] >= 'A' && companies[i][j] <= 'Z') {
here = companies[i][j] -'A';
}
else if(companies[i][j] >= 'a' && companies[i][j] <= 'z')
{
priority[here].push_back(companies[i][j]-'a');
}
else {
max_prior[here] = companies[i][j]-'0';
}
}
}
for(int i=0; i<applicants.size(); i++) {
int here = 0;
for(int j=0; j<applicants[i].size(); j++) {
if(applicants[i][j] >= 'a' && applicants[i][j] <= 'z') {
here = applicants[i][j] -'a';
}
else if(applicants[i][j] >= 'A' && applicants[i][j] <= 'Z')
{
need[here].push(applicants[i][j]-'A');
}
else {
max_need[here] = applicants[i][j]-'0';
}
}
}
memset(on_match, 0 , sizeof(on_match));
while(1) {
on_match_num = 0;
for(int i=0; i<26; i++) {
if(!need[i].empty() && !on_match[i] && max_need[i]) {
cur_app[need[i].front()][i] = true;
need[i].pop();
max_need[i]--;
}
}
memset(on_match, 0 , sizeof(on_match));
for(int i=0; i<26; i++) {
int amount = max_prior[i];
if(priority[i].empty()) continue;
for(int k=0; k<app_len; k++) {
if(cur_app[i][priority[i][k]]) {
amount--;
on_match[priority[i][k]] = true;
on_match_num++;
if(amount<=0) break;
}
}
}
for(int i=0; i<26; i++) {
for(int j=0; j<26; j++) {
if(!on_match[i]) cur_app[i][j] = false;
}
}
for(int i=0; i<app_len; i++) {
if(!max_need[i] && !on_match[i] && !on_done[i]) {
on_done_num++;
on_done[i] = true;
}
}
if(on_match_num+on_done_num >= applicants.size()) break;
}
vector<string> answer;
for(int i=0; i<comp_len; i++) {
string ii = "";
char a = 'A';
a+=i;
ii+=a;
ii+='_';
for(int j=0; j<26; j++) {
for(int i=0; i<26; i++){
{
char b = 'a';
b += i;
ii+=b;
}
}
}
answer.push_back(ii);
}
return answer;
}
int main() {
vector<string> maze = {"A fabdec 2", "B cebdfa 2", "C ecfadb 2"};
vector<string> appl = {"a BAC 1", "b BAC 3", "c BCA 2", "d ABC 3", "e BCA 3", "f ABC 2"};
vector<string> ans = solution(maze,appl);
for(int i=0; i<ans.size();i++) {
cout << ans[i] << endl;
}
}