118 lines
2.8 KiB
C
118 lines
2.8 KiB
C
#define _GNU_SOURCE
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <omp.h>
|
|
|
|
#define CHARS_MAX 512
|
|
#define MAX_RULES 2048
|
|
#define MAX_UPDATES 1024
|
|
#define MAX_PAGE_PER_UPDATE 1024
|
|
#define abs(a) ((a) < 0 ? (-(a)) : (a))
|
|
|
|
typedef struct rule {
|
|
int first;
|
|
int second;
|
|
} rule_t;
|
|
|
|
typedef struct update {
|
|
int* list;
|
|
int count;
|
|
} update_t;
|
|
|
|
typedef struct rule_list {
|
|
rule_t *rules;
|
|
int count;
|
|
} rule_list_t;
|
|
|
|
int cmp(const void*, const void*, void*);
|
|
|
|
int main() {
|
|
char *p, *buf, c;
|
|
|
|
buf = calloc(CHARS_MAX, sizeof(char));
|
|
p = buf;
|
|
int reading_rules = 1;
|
|
|
|
rule_t *rules = calloc(MAX_RULES, sizeof(rules[0]));
|
|
update_t *updates = calloc(MAX_UPDATES, sizeof(updates[0]));
|
|
|
|
int rule_count = 0, update_count = 0;
|
|
|
|
while ((c = getchar()) != EOF) {
|
|
*p++ = c;
|
|
if (c != '\n') {
|
|
continue;
|
|
}
|
|
|
|
if (buf[0] == '\n') {
|
|
reading_rules = 0;
|
|
} else if (reading_rules) {
|
|
sscanf(buf, "%i|%i", &rules[rule_count].first, &rules[rule_count].second);
|
|
rule_count++;
|
|
} else {
|
|
p = buf;
|
|
updates[update_count].list = calloc(MAX_PAGE_PER_UPDATE, sizeof(updates[0].list[0]));
|
|
do {
|
|
sscanf(p, "%i", &updates[update_count].list[updates[update_count].count]);
|
|
updates[update_count].count++;
|
|
// Find next , or \n
|
|
while (*p != ',' && *p != '\n') p++;
|
|
p++;
|
|
} while(*(p-1) != '\n');
|
|
update_count++;
|
|
}
|
|
|
|
memset(buf, 0, CHARS_MAX);
|
|
p = buf;
|
|
}
|
|
|
|
int count = 0;
|
|
int count2 = 0;
|
|
rule_list_t rule_list = {
|
|
.rules = rules,
|
|
.count = rule_count
|
|
};
|
|
#pragma omp parallel for
|
|
for (int i = 0; i < update_count; i++) {
|
|
int ordered = 1;
|
|
int *sorted = calloc(updates[i].count, updates[0].list[0]);
|
|
memcpy(sorted, updates[i].list, sizeof(updates[0].list[0]) * updates[i].count);
|
|
qsort_r(sorted, updates[i].count, sizeof(updates[0].list[0]), &cmp, &rule_list);
|
|
if (memcmp(sorted, updates[i].list, sizeof(updates[0].list[0]) * updates[i].count) == 0)
|
|
#pragma omp critical
|
|
{
|
|
count += updates[i].list[updates[i].count / 2];
|
|
}
|
|
else
|
|
#pragma omp critical
|
|
{
|
|
count2 += sorted[updates[i].count / 2];
|
|
}
|
|
}
|
|
|
|
free(buf);
|
|
free(rules);
|
|
for (int i = 0; i < update_count; i++) {
|
|
free(updates[i].list);
|
|
}
|
|
free(updates);
|
|
|
|
printf("%i\n", count);
|
|
printf("%i\n", count2);
|
|
}
|
|
|
|
int cmp(const void* a, const void* b, void *rulesp) {
|
|
rule_list_t rule_list = *(rule_list_t*)rulesp;
|
|
for (int i = 0; i < rule_list.count; i++) {
|
|
if (rule_list.rules[i].second == *(int*)a && rule_list.rules[i].first == *(int*)b) {
|
|
return 1;
|
|
}
|
|
if (rule_list.rules[i].first == *(int*)a && rule_list.rules[i].second == *(int*)b) {
|
|
return -1;
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|