Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
6.7 kB
3
Indexable
Never
#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 2