Untitled
plain_text
2 months ago
4.5 kB
2
Indexable
Never
#include <iostream> #include <string> #include <unordered_map> using namespace std; struct Node{ char data; Node* prev; Node* next; } pool[30000]; int idx; Node* getNode(){ return &pool[++idx]; } void connect(Node* a, Node* b){ a->next=b; b->prev=a; } class Linklist{ public: Node* head; Node* tail; void init(){ head=new Node(); tail=new Node(); connect(head, tail); } void addChar(Node *a){ Node* temp= tail->prev; connect(temp, a); connect(a, tail); } void addCharRV(Node *a){ Node* temp= head->next; connect(head, a); connect(a, temp); } void del(int K){ for(int i=0;i<K;i++){ Node* temp=tail->prev->prev; connect(temp, tail); } } void delRV(int K){ for(int i=0;i<K;i++){ Node* temp=head->next->next; connect(head, temp); } } } ll; string s; unordered_map<string, int> mh; int rv; void init(char mStr[]) { rv=0; ll.init(); mh.clear(); idx=0; string s=mStr; int len=s.size(); for(int i=0;i<len-3;i++){ Node* a=getNode(); a->data=s[i]; ll.addChar(a); string s1=""; for(int j=0;j<4;j++){ s1+=s[i+j]; mh[s1]++; } } Node* a=getNode(); a->data=s[len-3]; ll.addChar(a); string s2=""; for(int j=0;j<3;j++){ s2+=s[len-2+j]; mh[s2]++; } Node *b=getNode(); b->data=s[len-2]; ll.addChar(a); string s3=""; } void appendWord(char mWord[]) { string s=mWord; int len=s.size(); if(rv==0){ for(int i=0;i<len;i++){ Node* a= getNode(); a->data=s[i]; cc[getIndex(s[i])].push_back(a); ll.addChar(a); } } else{ for(int i=0;i<len;i++){ Node* a= getNode(); a->data=s[i]; cc[getIndex(s[i])].push_backRV(a); ll.addCharRV(a); } } } void cut(int k) { if(rv==0) ll.del(k); else ll.delRV(k); } void reverse() { rv=1-rv; } int countOccurrence(char mWord[]) { string s=mWord; int len=s.size(); int count=0; if(rv==0){ Node* cur=cc[getIndex(mWord[0])].headC->nextC; while(cur!= cc[getIndex(mWord[0])].tailC){ bool check=true; Node* cur1=cur; for(int i=0;i<len;i++){ if(cur1->data!=s[i]){ check=false; break; } cur1=cur1->next; } if(check==true) count++; cur=cur->nextC; } } else{ Node* cur=cc[getIndex(mWord[0])].tailC->prevC; while(cur!= cc[getIndex(mWord[0])].headC){ bool check=true; Node* cur1=cur; for(int i=0;i<len;i++){ if(cur1->data!=s[i]){ check=false; break; } cur1=cur1->prev; } if(check==true) count++; cur=cur->prevC; } } return count; } #ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include <stdio.h> #define CMD_INIT 1 #define CMD_APPEND 2 #define CMD_CUT 3 #define CMD_REVERSE 4 #define CMD_COUNT 5 extern void init(char mStr[]); extern void appendWord(char mWord[]); extern void cut(int k); extern void reverse(); extern int countOccurrence(char mWord[]); ///////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////// static bool run() { bool correct = false; int queryCnt; scanf("%d", &queryCnt); static char mStr[30001], mWord[5]; while (queryCnt--) { int cmd; scanf("%d", &cmd); if (cmd == CMD_INIT) { scanf("%s", mStr); init(mStr); correct = true; } else if (cmd == CMD_APPEND) { scanf("%s", mWord); if (correct) { appendWord(mWord); } } else if (cmd == CMD_CUT) { int k; scanf("%d", &k); if (correct) { cut(k); } } else if (cmd == CMD_REVERSE) { if (correct) { reverse(); } } else if (cmd == CMD_COUNT) { scanf("%s", mWord); int ret = -1; if (correct) { ret = countOccurrence(mWord); //printf("%d\n", ret); } int ans; scanf("%d", &ans); if(ret != ans) { correct = false; } } } return correct; } int main() { setbuf(stdout, NULL); freopen("sample_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; } 25 100 21 1 helloworld 5 o 2 5 owo 1 5 dh 0 5 hell 1 4 5 hell 0 5 owo 1 3 2 5 e 0 2 olol 5 lol 2 4 5 low 1 3 3 5 or 0 2 oooo 5 o 8 5 oo 4 5 ooo 3 5 oooo 2