Untitled
unknown
plain_text
2 years ago
42 kB
16
Indexable
//////////// Contact
import java.util.*;
public class UserSolution {
// KEY : data of field
// VALUE: N_records of 5-field -> can be duplicated -> save to list
HashMap<String, ArrayList<Info>>[] map;
class Info {
String[] value = new String[5];
boolean isDelete;
public Info(String... str) {
value = Arrays.copyOf(str,5);
isDelete = false;
}
}
public void InitDB() {
map = new HashMap[5];
for (int i = 0; i < 5; i++)
map[i] = new HashMap<String, ArrayList<Info>>();
}
public void Add(String... str) {
Info info = new Info(str);
for (int i = 0; i < 5; i++) {
ArrayList<Info> list = map[i].get(str[i]);
// not found -> init new for hash map
if (list == null) {
list = new ArrayList<Info>();
map[i].put(str[i], list);
}
// thêm tiếp các record cùng key
// nếu dùng else list.add(info) -> không thêm đc mà chỉ chạy vào hàm if
list.add(info);
}
}
public int Delete(int field, String str) {
int num = 0;
ArrayList<Info> list = map[field].get(str);
if (list != null) {
for (int i = 0; i < list.size(); i++) {
Info info = list.get(i);
if (info.isDelete == false){
num++;
info.isDelete = true;
}
}
return num;
}
return 0;
}
// Change(number, 777, email, 777@dcom) -> đổi email của all người có số 777 sang 777@dcom
// Search list-> delete all -> add new info
public int Change(int field, String str, int changefield, String changestr) {
int num = 0;
ArrayList<Info> list = map[field].get(str);
if (list != null) {
int size = list.size();
for (int i = 0; i < size; i++) {
Info info = list.get(i);
// xóa hết
if (info.isDelete == false) {
info.isDelete = true;
info.value[changefield] = changestr;
Add(info.value);
num++;
}
}
}
return num;
}
public int Change1(int field, String str, int changefield, String changestr) {
int num = 0;
ArrayList<Info> list = map[field].get(str);
ArrayList<Info> temp = new ArrayList<>();
if (list != null) {
int size = list.size();
for (int i = 0; i < size; i++) {
Info info = list.get(i);
// xóa hết
if (list.get(i).isDelete == false) {
temp.add(list.get(i));
num++;
}
}
// xoa va update thong tin truong can doi cua list doi tuong
for (Info info: temp) {
ArrayList<Info> changeInfo = map[changefield].get(info.value[changefield]);
changeInfo.remove(info);
info.value[changefield] = changestr;
ArrayList<Info> nChangeInfo = map[changefield].get(changestr);
if (nChangeInfo == null) {
nChangeInfo = new ArrayList<UserSolution.Info>();
map[changefield].put(changestr, nChangeInfo);
}
nChangeInfo.add(info);
}
}
return num;
}
// tìm số lượng ứng với điều kiện và trả về giá trị theo điều kiện nếu tìm được 1 bản ghi
// ví dụ Search(number,777,email) = tìm email của người có number = 777
public Solution.Result Search(int field, String str, int returnfield) {
Solution.Result result = new Solution.Result();
int num = 0;
ArrayList<Info> list = map[field].get(str);
if (list != null) {
for (int i = 0; i < list.size(); i++) {
Info info = list.get(i);
if (info.isDelete == false) {
num++;
result.str = info.value[returnfield];
}
}
result.count = num;
if (result.count != 1)
result.str = "NULL";
}
return result;
}
}
/// cach 2 : ko danh dau deleted
// cach 2
import java.util.*;
class UserSolution {
Map<String, Set<Record>> hashMap[] = new HashMap[5];
void InitDB() {
for (int i = 0; i < 5; i++)
hashMap[i] = new HashMap<>();
}
void Add(String... fields) {
Record record = new Record(fields);
for (int i = 0; i < fields.length; i++)
hashMap[i].computeIfAbsent(fields[i], k -> new HashSet<>()).add(record);
}
int Delete(int field, String str) {
Set<Record> records = hashMap[field].getOrDefault(str, new HashSet<>());
int size = records.size();
for (Record record : new HashSet<>(records))
for (int i = 0; i < 5; i++)
hashMap[i].get(record.field[i]).remove(record);
return size;
}
int Change(int field, String str, int changefield, String changestr) {
Set<Record> records = hashMap[field].getOrDefault(str, new HashSet<>());
int size = records.size();
for (Record record : new HashSet<>(records)) {
hashMap[changefield].get(record.field[changefield]).remove(record);
record.field[changefield] = changestr;
hashMap[changefield].computeIfAbsent(changestr, k -> new HashSet<>()).add(record);
}
return size;
}
Solution.Result Search(int field, String str, int returnfield) {
Solution.Result result = new Solution.Result();
Set<Record> records = hashMap[field].getOrDefault(str, new HashSet<>());
result.count = records.size();
if (records.size() == 1) {
Record record = (Record) records.toArray()[0];
result.str = record.field[returnfield];
}
return result;
}
}
class Record {
String field[];
Record(String... strings) {
field = Arrays.copyOf(strings, strings.length);
}
}
//// Gold mining camp
#include<stdio.h>
#define f(i,n) for(register int i=0;i<n;i++)
int N, A[20][20], B[20][20], v[20][20], g[4][2];
int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
void BFS(int x, int r, int c){
int q[400][3], h, t, l;
q[0][0] = r;
q[0][1] = c;
q[0][2] = 0;
h = t = 0;
v[r][c] |= x;
while(h<=t){
r = q[h][0];
c = q[h][1];
l = q[h++][2]+1;
f(i,4){
int a = r+d[i][0];
int b = c+d[i][1];
if(a>-1&&a<N&&b>-1&&b<N&&A[a][b]&&!(v[a][b]&x)){
v[a][b] |= x;
B[a][b]<l ? B[a][b]=l : 0;
q[++t][0] = a;
q[t][1] = b;
q[t][2] = l;
}
}
}
}
int main(){
int T, G, C, S;
scanf("%d", &T);
for(int tc = 1; tc <= T; ++tc){
scanf("%d\n%d", &N, &G);
f(i,G) scanf("%d %d", &g[i][0], &g[i][1]);
f(i,N) f(j,N){
scanf("%d", &A[i][j]);
v[i][j] = B[i][j] = 0;
}
f(i,G){
int r = g[i][0]-1;
int c = g[i][1]-1;
A[r][c] = 2;
BFS(1<<i,r,c);
}
S = (1<<G)-1;
C = 400;
f(i,N) f(j,N){
if(A[i][j]==1&&v[i][j]==S&&B[i][j]<C) C=B[i][j];
}
printf("Case #%d\n%d\n", tc, C);
}
return 0;
}
// linked list
Yêu cầu xây dựng một list các số nguyên, gồm các thao tác chính chèn, xóa và in. Các thao tác gồm có:
- f K: chèn vào đầu list số K.
- i j K: chèn vào vị trí j số K, (j >= 0, chỉ số vị trí được đánh số từ 0). Nếu j vượt quá vị trí của phần tử cuối cùng thì số đó được chèn vào cuối list.
- r: xóa phần tử đầu tiên của list. Nếu list rỗng thì không làm gì.
- d j: xóa phần tử ở vị trí j (j >= 0). Nếu j vượt quá vị trí của phần tử cuối cùng thì không làm gì.
- p j: in ra j phần tử đầu tiên của list (từ 0 đến j-1), nếu j vượt quá vị trí của phần tử cuối cùng thì in ra đến phần tử cuối cùng.
Input
Dòng đầu tiên là số lượng test case T. Thông tin về mỗi test case như sau:
- Dòng đầu tiên là số lượng thao tác N (N <= 30,000).
- N dòng tiếp theo là thông tin về các thao tác như mô tả ở trên.
Output
In ra các số tương ứng với mỗi thao tác in, nếu list rỗng in ra "empty" (trên cùng 1 dòng)
// cach 1
import java.util.Scanner;
class Solution {
static void slideArray(int index) {
for (int i = listSize; i > index; i--) {
nodeList[i] = nodeList[i - 1];
}
}
static void slideArrayPlus(int index) {
for (int i = index; i < listSize; i++) {
nodeList[i] = nodeList[i + 1];
}
}
static class Node {
int data;
Node back, front;
public Node(int data) {
this.data = data;
back = null;
front = null;
}
}
static void connect(Node n1, Node n2) {
n1.front = n2;
n2.back = n1;
}
static void addFirst(int data) {
node[nodeSize] = new Node(data);
if (listSize == 0) {
nodeList[0] = nodeSize;
nodeSize++;
listSize++;
return;
}
slideArray(0);
nodeList[0] = nodeSize;
connect(node[nodeList[0]], node[nodeList[1]]);
nodeSize++;
listSize++;
}
static void addIndex(int index, int data) {
if (index == 0) {
addFirst(data);
return;
}
node[nodeSize] = new Node(data);
if (listSize == 0) {
nodeList[0] = nodeSize;
nodeSize++;
listSize++;
return;
}
if (listSize < index) {
nodeList[listSize] = nodeSize;
connect(node[nodeList[listSize - 1]], node[nodeList[listSize]]);
nodeSize++;
listSize++;
return;
}
Node tmp = new Node(data);
slideArray(index);
connect(node[nodeList[index - 1]], tmp);
connect(tmp, node[nodeList[index + 1]]);
node[nodeSize] = tmp;
nodeList[index] = nodeSize;
nodeSize++;
listSize++;
}
static void delFirst() {
if (listSize == 0) {
return;
}
slideArrayPlus(0);
node[nodeList[0]].back = null;
listSize--;
}
static void delIndex(int index) {
if (index == 0) {
delFirst();
return;
}
if (listSize == 0 || index >= listSize) {
return;
}
slideArrayPlus(index);
connect(node[nodeList[index]], node[nodeList[index + 1]]);
listSize--;
}
static void show(int index) {
if (listSize == 0) {
System.out.print(" empty");
}
if (index > listSize) {
index = listSize;
}
for (int i = 0; i < index; i++) {
System.out.print(" " + node[nodeList[i]].data);
}
}
static char cmd;
static int n;
static Node[] node = new Node[30000];
static int[] nodeList = new int[30000];
static int listSize;
static int nodeSize;
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T;
T = sc.nextInt();
/*
* Read each test case from standard input.
*/
for (int test_case = 1; test_case <= T; test_case++) {
System.out.print("#" + test_case);
listSize = 0;
nodeSize = 0;
n = sc.nextInt();
for (int i = 0; i < n; i++) {
cmd = sc.next().charAt(0);
switch (cmd) {
case 'f':
addFirst(sc.nextInt());
break;
case 'i':
addIndex(sc.nextInt(), sc.nextInt());
break;
case 'r':
delFirst();
break;
case 'd':
delIndex(sc.nextInt());
break;
case 'p':
show(sc.nextInt());
break;
default:
break;
}
}
System.out.println();
}
}
}
// cach 2
#include <stdio.h>
#define MAX 100
#define SIZE 300
struct Node{
int V;
int next;
int prev;
}P[30000];
int c, C, t;
int H[MAX];
void add(int id, int v){
P[c].V = v;
id>C ? id=C : 0;
int x = id/SIZE;
int y = id%SIZE;
int n = H[x];
int p = n>-1 ? P[n].prev : t;
!y ? H[x] = c : 0;
while(y--){
p = n;
n = P[n].next;
}
p>-1 ? P[p].next = c : 0;
n>-1 ? P[n].prev = c : 0;
id==C ? t=c : 0;
P[c].next = n;
P[c++].prev = p;
C++;
for(int i=x+1;i<=C/SIZE;i++) H[i] = P[H[i]].prev;
C%SIZE==1 ? H[C/SIZE] = t : C%SIZE==0 ? H[C/SIZE] = -1 : 0;
}
void remove(int id){
if(id>=C) return;
int x = id/SIZE;
int y = id%SIZE;
int n = H[x];
int p = n>-1 ? P[n].prev : -1;
!y ? H[x] = P[n].next : 0;
while(y--){
p = n;
n = P[n].next;
}
if(n>-1){
p>-1 ? P[p].next = P[n].next : 0;
P[n].next>-1 ? P[P[n].next].prev = p : 0;
C--;
id==C ? t=P[t].prev : 0;
for(int i=x+1;i<=C/SIZE;i++) H[i] = P[H[i]].next;
C%SIZE==0 ? H[C/SIZE] = -1 : 0;
}
}
void print(int j){
if(!C) printf(" empty");
else{
int n = H[0];
while(n>-1&&j--){
printf(" %d", P[n].V);
n = P[n].next;
}
}
}
int main(){
int T, N, j, k;
char cmd[2];
scanf("%d", &T);
for(int tc=1; tc<=T; tc++){
printf("#%d", tc);
H[0] = -1;
c = C = 0;
t = -1;
scanf("%d", &N);
while(N>0){
scanf("%s", &cmd);
switch(cmd[0]){
case'd':
scanf("%d", &j);
remove(j);
break;
case'f':
scanf("%d", &k);
add(0, k);
break;
case'i':
scanf("%d%d", &j, &k);
add(j, k);
break;
case'p':
scanf("%d", &j);
print(j);
break;
case'r':
remove(0);
break;
}
N--;
}
printf("\n");
}
return 0;
}
// subway line
import java.util.*;
class UserSolution {
static final int LINE_NUM = 5;
class Station {
int id, line, visitTime, timeElapsed;
Station next, prev;
public Station(int line, int id) {
this.line = line;
this.id = id;
visitTime = timeElapsed = 0;
}
}
HashMap<Integer, ArrayList<Station>> mHashStation;
boolean[][] mIsLineConnect;
int mTime;
public void init(int N, int mLastStation1[], int mLastStation2[]) {
mHashStation = new HashMap<Integer, ArrayList<Station>>();
mIsLineConnect = new boolean[5][5];
mTime = 0;
for (int line = 0; line < LINE_NUM; line++) {
add(line, -1, mLastStation1[line]);
add(line, mLastStation1[line], mLastStation2[line]);
}
}
public void add(int mLine, int mPrevStation, int mStation) {
Station newStation = new Station(mLine, mStation);
// insert into linked list
if (mPrevStation == -1) {
newStation.next = null;
newStation.prev = null;
} else {
Station prevStation = getStationOnLine(mLine, mPrevStation);
Station nextStation = prevStation.next;
newStation.next = nextStation;
newStation.prev = prevStation;
prevStation.next = newStation;
if (nextStation != null)
nextStation.prev = newStation;
}
// add to hash table for quick find
if (!mHashStation.containsKey(mStation))
mHashStation.put(mStation, new ArrayList<Station>());
ArrayList<Station> dupStations = mHashStation.get(mStation);
dupStations.add(newStation);
// update relationship between lines
for (Station st : dupStations) {
mIsLineConnect[st.line][mLine] = true;
mIsLineConnect[mLine][st.line] = true;
}
}
public Station getStationOnLine(int line, int stationID) {
for (Station st : mHashStation.get(stationID)) {
if (st.line == line)
return st;
}
return null;
}
public int minTravelTime(int mStartStation, int mEndStation) {
int minTravel = Integer.MAX_VALUE;
// There are multiple instances with id mStartStation with different
// line,
// we would have to start from all of them to choose the min time.
ArrayList<Station> arrStations = mHashStation.get(mStartStation);
if (arrStations == null)
return -1;
for (Station st : arrStations) {
int travel = minTravelTime(st, mEndStation);
if (travel < minTravel)
minTravel = travel;
}
return minTravel == Integer.MAX_VALUE ? -1 : minTravel;
}
public int minTravelTime(Station startStation, int mEndStation) {
mTime++;
Queue<Station> queue = new LinkedList<Station>();
queue.add(startStation);
startStation.timeElapsed = 0;
while (!queue.isEmpty()) {
Station curStation = queue.poll();
if (curStation.id == mEndStation)
return curStation.timeElapsed;
// find all reachable station (prev, next, same station in other
// line)
ArrayList<Station> reachableStations = new ArrayList<>();
reachableStations.add(curStation.next);
reachableStations.add(curStation.prev);
for (Station otherLineStation : mHashStation.get(curStation.id)) {
reachableStations.add(otherLineStation);
}
// check visit, update time and add into queue
for (Station otherStation : reachableStations) {
if (otherStation != null && otherStation.visitTime != mTime) {
otherStation.visitTime = mTime;
otherStation.timeElapsed = curStation.timeElapsed + 1;
queue.add(otherStation);
}
}
}
return Integer.MAX_VALUE;
}
public int minTransfer(int mStartStation, int mEndStation) {
int minTransfer = Integer.MAX_VALUE;
ArrayList<Station> listStartStations = mHashStation.get(mStartStation);
ArrayList<Station> listEndStations = mHashStation.get(mEndStation);
if (listStartStations == null || listEndStations == null)
return -1;
// Generate startLine and endLine pair to find min transfer
for (Station startStation : listStartStations) {
for (Station endStation : listEndStations) {
if (startStation.line == endStation.line)
return 0;
else {
int transfer = minTransferLine(startStation.line, endStation.line);
if (transfer < minTransfer)
minTransfer = transfer;
}
}
}
return minTransfer == Integer.MAX_VALUE ? -1 : minTransfer;
}
public int minTransferLine(int startLine, int endLine) {
int[] visited = new int[5];
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(startLine);
visited[startLine] = 1;
while (!queue.isEmpty()) {
int line = queue.poll();
if (line == endLine)
return visited[line] - 1;
for (int otherLine = 0; otherLine < LINE_NUM; otherLine++) {
if (mIsLineConnect[line][otherLine] && visited[otherLine] == 0) {
visited[otherLine] = visited[line] + 1;
queue.add(otherLine);
}
}
}
return Integer.MAX_VALUE;
}
}
//c2
import java.util.*;
class UserSolution {
int MAX_STATION = 40000;
int MAX_LINE = 5;
int time = 0;
Station[][] stationMap = new Station[MAX_STATION][MAX_LINE];
boolean[][] isLineConnect = new boolean[MAX_LINE][MAX_LINE];
int[] transfer = new int[5];
Queue<Station> StationQ = new ArrayDeque<>();
Queue<Integer> QTransfer = new ArrayDeque<>();
static class Station {
int id, line, time, timeElapsed;
Station next, prev;
Station(int id, int line) {
this.id = id;
this.line = line;
}
}
public void init(int N, int mLastStation1[], int mLastStation2[]) {
for (int i = 0; i < N; i++)
for (int j = 0; j < MAX_LINE; j++)
stationMap[i][j] = null;
for (int i = 0; i < MAX_LINE; i++)
for (int j = 0; j < MAX_LINE; j++)
isLineConnect[i][j] = (i == j);
for (int line = 0; line < MAX_LINE; line++) {
int sid = mLastStation1[line];
int eid = mLastStation2[line];
stationMap[sid][line] = new Station(sid, line);
stationMap[eid][line] = new Station(eid, line);
addStation(line, null, stationMap[eid][line], stationMap[sid][line]);
addStation(line, stationMap[sid][line], null, stationMap[eid][line]);
}
}
void addStation(int line, Station pre, Station next, Station temp) {
temp.prev = pre;
if (pre != null) {
pre.next = temp;
}
temp.next = next;
if (next != null) {
next.prev = temp;
}
for (int otherLine = 0; otherLine < MAX_LINE; otherLine++) {
if (stationMap[temp.id][otherLine] != null)
isLineConnect[line][otherLine] = isLineConnect[otherLine][line] = true;
}
}
public void add(int mLine, int mPrevStation, int mStation) {
stationMap[mStation][mLine] = new Station(mStation, mLine);
Station pre = stationMap[mPrevStation][mLine];
Station next = pre.next;
addStation(mLine, pre, next, stationMap[mStation][mLine]);
}
public int minTravelTime(int mStartStation, int mEndStation) {
time++;
StationQ.clear();
for (int i = 0; i < MAX_LINE; i++)
addQueue(stationMap[mStartStation][i], 0);
while (!StationQ.isEmpty()) {
Station sta = StationQ.poll();
if (sta.id == mEndStation)
return sta.timeElapsed;
addQueue(sta.prev, sta.timeElapsed + 1);
addQueue(sta.next, sta.timeElapsed + 1);
for (int i = 0; i < MAX_LINE; i++)
addQueue(stationMap[sta.id][i], sta.timeElapsed + 1);
}
return -1;
}
void addQueue(Station n, int dis) {
if (n != null && n.time != time) {
n.time = time;
n.timeElapsed = dis;
StationQ.add(n);
}
}
public int minTransfer(int mStartStation, int mEndStation) {
QTransfer.clear();
boolean[] endS = new boolean[MAX_LINE];
for (int i = 0; i < MAX_LINE; i++) {
transfer[i] = -1;
if (stationMap[mEndStation][i] != null)
endS[i] = true;
if (stationMap[mStartStation][i] != null) {
QTransfer.add(i);
transfer[i] = 0;
}
}
while (!QTransfer.isEmpty()) {
int line = QTransfer.poll();
int time = transfer[line];
if (endS[line])
return transfer[line];
for (int i = 0; i < MAX_LINE; i++) {
if (isLineConnect[line][i] && transfer[i] == -1) {
QTransfer.add(i);
transfer[i] = time + 1;
}
}
}
return -1;
}
}
//c3
#define MAX 40000
#define f(i,x,n) for(register int i=x;i<n;i++)
int tcase = 0, map[5][5], mN;
int D[MAX], Q[MAX][3], h, t;
struct Node{
int cnt, next[5], prev[5];
bool sub[5];
void rs(){
cnt = tcase;
f(i,0,5){
next[i] = prev[i] = -1;
sub[i] = 0;
}
}
void mapSub(int i){
f(j,0,5) if(i!=j&&sub[j]) map[i][j] = map[j][i] = 1;
}
}P[MAX];
void init(int N, int mLastStation1[5], int mLastStation2[5]){
mN = N;
tcase++;
f(i,0,5) {
P[mLastStation1[i]].rs();
P[mLastStation2[i]].rs();
f(j,0,5) map[i][j] = 0;
}
f(i,0,5){
P[mLastStation1[i]].next[i] = mLastStation2[i];
P[mLastStation1[i]].sub[i] = 1;
P[mLastStation2[i]].prev[i] = mLastStation1[i];
P[mLastStation2[i]].sub[i] = 1;
f(j,0,i){
if(P[mLastStation1[i]].sub[j]||P[mLastStation2[i]].sub[j]) map[i][j] = map[j][i] = 1;
}
}
}
void add(int mLine, int mPrevStation, int mStation){
bool newS = 0;
if(P[mStation].cnt<tcase){
newS = 1;
P[mStation].rs();
}
P[mStation].next[mLine] = P[mPrevStation].next[mLine];
P[mStation].prev[mLine] = mPrevStation;
P[P[mPrevStation].next[mLine]].prev[mLine] = mStation;
P[mPrevStation].next[mLine] = mStation;
if(!newS&&!P[mStation].sub[mLine]) P[mStation].mapSub(mLine);
P[mStation].sub[mLine] = 1;
}
int minTravelTime(int mStartStation, int mEndStation){
if(mStartStation==mEndStation) return 0;
if(P[mStartStation].cnt<tcase||P[mEndStation].cnt<tcase) return -1;
int ans = MAX;
f(i,0,mN) D[i] = MAX;
t = 1;
h = 0;
Q[0][0] = mStartStation;
Q[0][1] = 0;
Q[0][2] = -1;
D[mStartStation] = 0;
while(h<t){
int s = Q[h][0];
int d = Q[h][1]+1;
int l = Q[h++][2];
f(i,0,5){
int d1 = l<0||i==l ? d : d+1;
if(P[s].prev[i]==mEndStation){if(ans>d1) ans = d1;}
else if(P[s].prev[i]>-1&&D[P[s].prev[i]]>=d1){
D[P[s].prev[i]] = d1;
Q[t][0] = P[s].prev[i];
Q[t][1] = d1;
Q[t++][2] = i;
}
if(P[s].next[i]==mEndStation){if(ans>d1) ans = d1;}
else if(P[s].next[i]>-1&&D[P[s].next[i]]>=d1){
D[P[s].next[i]] = d1;
Q[t][0] = P[s].next[i];
Q[t][1] = d1;
Q[t++][2] = i;
}
}
}
return ans<MAX ? ans : -1;
}
int minTransfer(int mStartStation, int mEndStation){
if(P[mStartStation].cnt<tcase||P[mEndStation].cnt<tcase) return -1;
int A[5];
f(i,0,5) A[i] = 0;
int h = t = 0;
f(i,0,5){
if(P[mStartStation].sub[i]){
if(P[mEndStation].sub[i]) return 0;
A[i] = 1;
Q[t][0] = i;
Q[t++][1] = 1;
}
}
while(h<t){
int l = Q[h][0];
int d = Q[h++][1];
f(i,0,5) if(!A[i]&&map[l][i]){
if(P[mEndStation].sub[i]) return d;
A[i] = 1;
Q[t][0] = i;
Q[t++][1] = d+1;
}
}
return -1;
}
/// quan ly nhan nhan-
You are required to write a program that manages soldiers.
Each solider has an identification number, team, and reputation score.
The program must have the following features:
1. Recruit soldiers
2. Fire soldiers
3. Change the reputation scores of soldiers
4. Change all the reputation scores of soldiers in a particular team
5. Search for a solider with the highest reputation score within a particular team
Implement each required function by referring to the following API description.
※ The function signature below is based on C/C++. As for Java, refer to the provided Solution.java and UserSolution.java.
The following is the description of API to be written in the User Code.
void init()
This function is called in each test case.
There are no recruited soldiers in the beginning of the test case.
void hire(int mID, int mTeam, int mScore)
This function recruits a solider whose identification number is mID, team is mTeam, and reputation score is mScore.
It is guaranteed that one solider can only be recruited once in a test case.
Parameters
mID : Identification number (1 ≤ mID ≤ 100,000)
mTeam : Team of the soldier (1 ≤ mTeam ≤ 5)
mScore : Reputation score (1 ≤ mScore ≤ 5)
void fire(int mID)
This function fires a solider whose identification number is mID.
It is guaranteed that mID has been recruited when fire() is called.
Parameters
mID : Identification number (1 ≤ mID ≤ 100,000)
void updateSoldier(int mID, int mScore)
This function changes the reputation score of mID to mScore.
It is guaranteed that mID has been recruited when this function is called.
Parameters
mID : Identification number (1 ≤ mID ≤ 100,000)
mScore : Reputation score (1 ≤ mScore ≤ 5)
void updateTeam(int mTeam, int mChangeScore)
This function changes all the reputation scores of soldiers in a team named mTeam.
It is guaranteed that there are one or more recruited soldiers in mTeam.
Scores are changed by updateTeam() according to the following rules:
If ‘the score before change + mChangeScore’ is larger than 5, change the score to 5.
If ‘the score before change + mChangeScore’ is less than 1, change the score to 1.
In other cases, change the score to ‘the score before change + mChangeScore.’
Parameters
mTeam : Name of the team (1 ≤ mTeam ≤ 5)
mChangeScore : Reputation score to be added (-4 ≤ mChangeScore ≤ 4)
int bestSoldier(int mTeam)
This function returns the identification number of a soldier with the highest reputation score among the ones in mTeam.
If more than one soldier has the highest score, return the largest identification number.
It is guaranteed that there are one or more recruited soldiers in mTeam.
Parameters
mTeam : Name of the team (1 ≤ mTeam ≤ 5)
Returns
Identification number of the solider with the highest reputation score
///c1
#define MAX 100001
struct Node{
int team;
int next, prev;
}P[MAX];
struct Team{
int h[6];
int t[6];
}T[6];
void init(){
for(int i=1;i<6;i++)
for(int j=1;j<6;j++) T[i].h[j] = T[i].t[j] = -1;
}
void hire(int mID, int mTeam, int mScore){
P[mID].team = mTeam;
P[mID].next = -1;
if(T[mTeam].h[mScore]<0){
T[mTeam].h[mScore] = T[mTeam].t[mScore] = mID;
P[mID].prev = -1;
}else{
P[mID].prev = T[mTeam].t[mScore];
P[T[mTeam].t[mScore]].next = mID;
T[mTeam].t[mScore] = mID;
}
}
void fire(int mID){
if(P[mID].prev<0){
for(int i=1;i<6;i++){
if(T[P[mID].team].h[i]==mID){
T[P[mID].team].h[i] = P[mID].next;
P[mID].next>-1 ? P[P[mID].next].prev = -1 : T[P[mID].team].t[i]=-1;
break;
}
}
}else{
P[P[mID].prev].next = P[mID].next;
P[mID].next>-1 ? P[P[mID].next].prev = P[mID].prev : 0;
}
for(int i=1;i<6;i++)
T[P[mID].team].t[i]==mID ? T[P[mID].team].t[i]=P[mID].prev : 0;
}
void updateSoldier(int mID, int mScore){
fire(mID);
hire(mID, P[mID].team, mScore);
}
void updateTeam(int mTeam, int mChangeScore){
int h[6], t[6];
for(int i=1;i<6;i++) h[i] = t[i] = -1;
for(int i=1;i<6;i++){
if(T[mTeam].h[i]<0) continue;
int j = i+mChangeScore;
j<1 ? j=1 : j>5 ? j=5 : 0;
if(h[j]<0){
h[j] = T[mTeam].h[i];
t[j] = T[mTeam].t[i];
}else{
P[t[j]].next = T[mTeam].h[i];
P[T[mTeam].h[i]].prev = t[j];
t[j] = T[mTeam].t[i];
}
}
for(int i=1;i<6;i++){
T[mTeam].h[i] = h[i];
T[mTeam].t[i] = t[i];
}
}
int bestSoldier(int mTeam){
int ID = -1;
for(int i=5;i>0;i--){
if(T[mTeam].h[i]<0) continue;
int id = T[mTeam].h[i];
while(id>-1){
ID<id ? ID=id : 0;
id = P[id].next;
}
break;
}
return ID;
}
//c2
#define FAST __attribute__((optimize("Ofast")))
struct Node{
int id,team;
Node* next;
Node* prev;
} ;
Node Solider[100001];
struct team{
Node score[6];
int postion[6];
};
team Team[6];
FAST void addNode(Node* head, Node* temp)
{
temp->prev = head;
temp->next = head->next;
head->next->prev = temp;
head->next = temp;
}
FAST void delNode(Node* head)
{
head->next->prev=head->prev;
head->prev->next = head->next;
}
FAST void init()
{
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
Team[i].score[j].prev=&Team[i].score[j];
Team[i].score[j].next=&Team[i].score[j];
}
}
for(int i=1;i<=5;i++)
for(int j=1;j<=5;j++)
Team[i].postion[j]=j;
}
FAST void hire(int mID, int mTeam, int mScore)
{
Solider[mID].id=mID;
Solider[mID].team=mTeam;
addNode(Team[mTeam].score[mScore].prev,&Solider[mID]);
}
FAST void fire(int mID)
{
delNode(&Solider[mID]);
}
FAST void updateSoldier(int mID, int mScore)
{
int team=Solider[mID].team;
delNode(&Solider[mID]);
addNode(Team[team].score[mScore].prev,&Solider[mID]);
}
FAST void updateTeam(int mTeam, int mChangeScore)
{
Node *arr[6][2];
int isnull[6];
for(int i=1;i<=5;i++)
{
isnull[i]=1;
if(Team[mTeam].score[i].next != &Team[mTeam].score[i])
{
arr[i][0]=Team[mTeam].score[i].next;
arr[i][1]=Team[mTeam].score[i].prev;
Team[mTeam].score[i].prev=Team[mTeam].score[i].next=&Team[mTeam].score[i];
}
else isnull[i]=0;
}
for(int i=1;i<=5;i++)
{
int nScore= i+mChangeScore;
nScore = nScore > 5 ? 5:nScore;
nScore = nScore < 1 ? 1:nScore;
if(isnull[i]!=0)
{
arr[i][0]->prev=&Team[mTeam].score[nScore];
arr[i][1]->next=Team[mTeam].score[nScore].next;
Team[mTeam].score[nScore].next->prev=arr[i][1];
Team[mTeam].score[nScore].next=arr[i][0];
arr[i][0]=0;
}
}
}
FAST int bestSoldier(int mTeam)
{
int max=0;
for(int i=5;i>=1;i--)
{
int check=0;
Node* temp=Team[mTeam].score[i].next;
while(temp!=&Team[mTeam].score[i])
{
check=1;
if(temp->id>max) max=temp->id;
temp=temp->next;
}
if(check==1) break;
}
return max;
}
//c3
import java.util.*;
class UserSolution
{
User[] arr;
list[][] teams;
class User{
int id;
int team;
User next, pre;
User(int id,int team){
this.id = id;
this.team = team;
}
}
class list{
User head;
User tail;
public list(){
this.head = new User(0,0);
this.tail = new User(0,0);
head.next = tail;
tail.pre = head;
}
void add(User user){
tail.pre.next = user;
user.pre = tail.pre;
tail.pre = user;
user.next = tail;
}
void addAll(list l){
tail.pre.next = l.head.next;
l.head.next.pre = tail.pre;
l.tail.next = tail;
tail.pre = l.tail;
}
}
public void init()
{
arr = new User[100001];
teams = new list[6][6];
for (int i = 1; i <6; i++)
for (int j = 1; j < 6; j++){
teams[i][j] = new list();
}
}
public void hire(int mID, int mTeam, int mScore)
{
User u = new User( mID, mTeam);
arr[mID] = u;
teams[mTeam][mScore].add(u);
}
public void fire(int mID)
{
User u = arr[mID];
u.pre.next = u.next;
u.next.pre = u.pre;
}
public void updateSoldier(int mID, int mScore)
{
fire(mID);
hire(mID,arr[mID].team,mScore);
}
public void link(User a, User b){
a.next = b;
b.pre = a;
}
public void update(int team, int oldScore, int newScore){
link(teams[team][newScore].tail.pre,teams[team][oldScore].head.next);
link(teams[team][oldScore].tail.pre,teams[team][newScore].tail);
link(teams[team][oldScore].head,teams[team][oldScore].tail);
}
public void updateTeam(int mTeam, int mChangeScore)
{
if(mChangeScore > 0){
for(int i = 4; i>=1; i--){
int newScore = i + mChangeScore;
if(newScore > 5) newScore = 5;
teams[mTeam][newScore].addAll(teams[mTeam][i]);
teams[mTeam][i]=new list();
}
}else if(mChangeScore < 0){
for(int i = 2; i<=5; i++){
int newScore = i + mChangeScore;
if(newScore < 1) newScore = 1;
teams[mTeam][newScore].addAll(teams[mTeam][i]);
teams[mTeam][i]=new list();
}
}
}
public int bestSoldier(int mTeam)
{
int max = 0;
boolean found = false;
for (int i = 5; i>= 1; i--){
list l = teams[mTeam][i];
if (l.head.next == l.tail) continue;
User u = l.head;
while(u!=l.tail){
if (u.id > max){
max = u.id;
found = true;
}
u = u.next;
}
if (found) return max;
}
return max;
}
}
Editor is loading...