Untitled
unknown
plain_text
2 years ago
6.7 kB
6
Indexable
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#define MAX_LEN 10
void init(int N);
int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[]);
int checkString(int mTimestamp, int mLen);
#define CMD_INIT 100
#define CMD_GEN 200
#define CMD_CHECK 300
static bool run()
{
int query_num;
scanf("%d", &query_num);
int ret, ans;
bool ok = false;
for (int q = 0; q < query_num; q++)
{
int query;
scanf("%d", &query);
if (query == CMD_INIT)
{
int N;
scanf("%d", &N);
init(N);
ok = true;
}
else if (query == CMD_GEN)
{
int mTimestamp;
int mLifespan, mLen;
char mStr[MAX_LEN+1];
scanf("%d %d %d %s", &mTimestamp, &mLifespan, &mLen, mStr);
ret = generateString(mTimestamp, mLifespan, mLen, mStr);
scanf("%d", &ans);
if (ans != ret)
{
ok = false;
}
}
else if (query == CMD_CHECK)
{
int mTimestamp, mLen;
int ans;
scanf("%d %d", &mTimestamp, &mLen);
ret = checkString(mTimestamp, mLen);
scanf("%d", &ans);
if (ans != ret){
ok = false;
}
}
}
return ok;
}
int main()
{
setbuf(stdout, NULL);
freopen("input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++)
{
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
#define MAP_SIZE 32*32*32
#define STRING_SIZE 11001
#define NULL 0
struct LinkedList {
LinkedList* next;
int id;
LinkedList(int id, LinkedList* next) {
this->id = id;
this->next = next;
}
};
struct Str {
int union_id;// goc friend
int deadtime;// time die
};
LinkedList* list[11]; //luu cac string co length = index
int map[MAP_SIZE]; //luu hash cua cac substring cos length = 3
Str str[STRING_SIZE]; //luu data cua cac String
int string_count; //luu so luong string da duoc them vao
void init(int N)
{
string_count = 0;
for(int i = 5; i < 11; i++) {
list[i] = new LinkedList(-1, NULL);
}
for(int i = 0; i < MAP_SIZE; i++) {
map[i] = -1;
}
for(int i = 0; i < STRING_SIZE; i++) {
str[i].union_id = -1;
}
}
int checkString(int mTimestamp, int mLen)
{
int result = 0;
LinkedList *temp = list[mLen];
//duyet het list cac string co do dai = mLen
while(temp->next != NULL) {
//tim den union lead goc cua string dang duyet
int str_id = temp->next->id;// truy cap id cua phan tu thu 2 trong list ma con tro temp tro toi
int union_id = str[str_id].union_id;
while(str[union_id].union_id != union_id) union_id = str[union_id].union_id;
//Neu union do da dead thi xoa string khoi list
if(str[union_id].deadtime <= mTimestamp) {
LinkedList * deleted_str = temp->next;
temp->next = temp->next->next;
delete deleted_str;
} else { //neu union con ton tai thi tang result, duyet sang string tiep theo
result++;
temp = temp->next;
}
}
return result;
}
int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[])
{
int hash_index; //index cua substring
for(int i = 0; i <= mLen - 3; i++) {
hash_index = 0;
for(int j = 0; j < 3; j++) {
hash_index = (hash_index << 5) | (mStr[i + j] - 'a');// chuyen sang nhi phan dich bit 5 buoc roi luu gia tri '' -'a' (0-27 o dang nhi phan) roi chuyen thapphan
}
if(map[hash_index] != -1) { //substring da ton tai trong cac string truoc do
//tim den union lead goc cua union chua substring do
int union_lead = map[hash_index];
while(str[union_lead].union_id != union_lead) union_lead = str[union_lead].union_id;
if(str[union_lead].deadtime <= mTimestamp) { //union do da dead
goto addNew;
} else {
if(str[string_count].union_id == -1) { //string moi chua duoc gan vao 1 union nao ca
//gan string moi vao union lead nay va update deadtime cua union lead
str[string_count].union_id =union_lead;
str[union_lead].deadtime = mTimestamp + mLifespan;
} else { //string moi da duoc gan vao 1 union truoc do
//gop union cua union lead sang union truoc do cua string moi
str[union_lead].union_id = str[string_count].union_id;
}
}
} else { //substring chua ton tai trong string nao truoc do thi add new voi id cua string moi
addNew: map[hash_index] = string_count;
}
}
//Neu duyet het substring nhung string moi khong duoc gan vao union nao
//thi gan string moi vao union cua chinh no
if(str[string_count].union_id == -1) {
str[string_count].union_id = string_count;
str[string_count].deadtime = mTimestamp + mLifespan;
}
//Add string moi vao list cac string co do dai = mLen
LinkedList *newStr = new LinkedList(string_count, list[mLen]->next);
list[mLen]->next = newStr;
string_count++;
return checkString(mTimestamp, mLen);
}
25 100
20
100 7
300 1 5 0
200 2 4 6 member 1
200 4 5 6 barber 2
200 6 5 6 memory 3
200 8 10 7 carguer 1
200 10 5 7 embargo 2
300 14 6 3
200 15 2 6 langue 1
300 16 7 0
200 21 5 6 banana 1
200 25 5 6 banana 2
200 29 2 6 banana 3
300 30 6 3
200 31 2 6 banana 1
200 33 2 5 aacbb 1
200 34 2 6 aaccbb 1
200 35 2 7 aacxcbb 1
300 36 6 1
300 37 6 0
16
100 5
200 3 14 5 anxht 1
200 6 14 5 anxhn 2
200 7 3 5 mznmr 3
300 10 5 2
300 14 5 2
200 19 13 5 rznmr 3
300 21 5 1
200 22 12 5 rhanm 2
200 25 5 5 nxtan 3
200 26 12 5 mznmm 4
300 28 5 4
200 29 16 5 hmrhm 5
300 31 5 4
200 33 19 5 mznmr 5
200 38 2 5 znmrh 5
21
100 6
200 1 4 5 nganz 1
200 4 6 5 bgmzo 2
200 8 3 6 bganzm 1
200 11 20 5 bganz 1
300 12 6 0
300 15 6 0
200 18 8 6 loanlo 1
200 22 10 6 nzvnlo 2
300 24 5 1
200 25 6 5 agaxb 2
200 26 16 6 xbgana 3
300 31 6 3
200 33 16 5 nzvnx 2
300 34 6 1
200 35 4 6 mxbgbg 2
200 36 17 5 nzzmx 3
200 39 12 6 ganblo 1
200 43 2 6 vnloab 2
200 48 13 5 zvnlz 3
200 52 10 5 ganzv 4
111
100 7
200 5 15 7 phegwav 1
200 7 13 6 avaphp 1
200 8 6 5 rcfhe 1
300 13 6 1
300 18 7 1
200 20 8 5 phetw 1
200 23 2 5 drcfk 2
200 28 2 5 drgwd 1
200 32 18 7 tdetdrp 1
200 36 2 7 etdrcfw 2
200 37 10 7 hetdrcf 3
200 38 2 7 phetdrh 4
200 43 4 6 phethe 1
200 48 12 7 fvapphe 1
200 51 17 5 hetdd 1
200 54 20 5 avete 2
200 56 9 7 hettdar 2
200 61 15 7 tdrcfkr 2
200 63 9 7 etdrcfk 3
200 68 16 6 wavgwh 1
200 73 8 7 tdrcphe 1
200 77 18 5 vawav 1
200 81 9 7 phtdrap 1
200 86 4 6 hetdcf 2
200 88 7 7 avaphev 2
200 93 3 7 phetdrt 2Editor is loading...