Codeforces Round #390 (Div. 2), problem: (C) Vladik and Chat Solution in C/C++

Codeforces Round #390 (Div. 2), problem: (C) Vladik and Chat Solution in C/C++

#include <stdio.h>
#include <string.h>

int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, m;
        scanf("%d", &n);
        char Name[100][11];
        for(int i = 0; i < n; ++i) {
            scanf("%s", Name[i]);
        }
        scanf("%d\n", &m);
        char Msg[100][132];
        char Flag[100][100];
        int Cnt[100];
        int Ans[100];
        memset(Ans, -1, sizeof(Ans));
        memset(Cnt, 0, sizeof(Cnt));
        memset(Flag, 0, sizeof(Flag));
        for(int i = 0; i < m; ++i) {
            fgets(Msg[i], 131, stdin);
            if(Msg[i][0] == '?') {
                Cnt[i] = n;
                int start = 1;
                int end;
                while(Msg[i][start] != '\0') {
                    if((Msg[i][start] >= 'a' && Msg[i][start] <= 'z') || (Msg[i][start] >= 'A' && Msg[i][start] <= 'Z') || (Msg[i][start] >= '0' && Msg[i][start] <= '9')) {
                        int end = start;
                        while(Msg[i][end] != '\0') {
                            if((Msg[i][end] >= 'a' && Msg[i][end] <= 'z') || (Msg[i][end] >= 'A' && Msg[i][end] <= 'Z') || (Msg[i][end] >= '0' && Msg[i][end] <= '9')) {
                                ++end;
                            } else {
                                break;
                            }
                        }
                        char subStr[101];
                        int len = 0;
                        for(int j = start; j < end; ++j) {
                            subStr[len++] = Msg[i][j];
                        }
                        subStr[len] = '\0';
                        for(int j = 0; j < n; ++j) {
                            if(strcmp(subStr, Name[j]) == 0) {
                                if(Flag[i][j] == 0) {
                                    Flag[i][j] = -1;
                                    --Cnt[i];
                                    break;
                                }
                            }
                        }
                        start = end;
                    } else {
                        ++start;
                    }
                }
                if(Cnt[i] == 1) {
                    for(int j = 0; j < n; ++j) {
                        if(Flag[i][j] == 0) {
                            Ans[i] = j;
                            break;
                        }
                    }
                }
            } else {
                memset(Flag[i], -1, 100 * sizeof(char));
                char curName[11];
                int len = 0;
                for(int j = 0; Msg[i][j] != ':'; ++j) {
                    curName[len++] = Msg[i][j];
                }
                curName[len] = '\0';
                Cnt[i] = 1;
                for(int j = 0; j < n; ++j) {
                    if(strcmp(curName, Name[j]) == 0) {
                        Flag[i][j] = 0;
                        Ans[i] = j;
                        break;
                    }
                }
            }
        }
        for(int i = 0; i < m; ++i) {
            if(Cnt[i] == 1) {
                int cur = i;
                while(cur - 1 >= 0 && Flag[cur - 1][Ans[cur]] == 0) {
                    Flag[cur - 1][Ans[cur]] = -1;
                    if(--Cnt[cur - 1] != 1) {
                        break;
                    }
                    for(int j = 0; j < n; ++j) {
                        if(Flag[cur - 1][j] == 0) {
                            Ans[cur - 1] = j;
                            break;
                        }
                    }
                    --cur;
                }
                cur = i;
                while(cur + 1 < m && Flag[cur + 1][Ans[cur]] == 0) {
                    Flag[cur + 1][Ans[cur]] = -1;
                    if(--Cnt[cur + 1] != 1) {
                        break;
                    }
                    for(int j = 0; j < n; ++j) {
                        if(Flag[cur + 1][j] == 0) {
                            Ans[cur + 1] = j;
                            break;
                        }
                    }
                    ++cur;
                }
            }
        }
        char Impossible = 0;
        for(int i = 0; i < m; ++i) {
            if(Cnt[i] == 0) {
                Impossible = 1;
            }
        }
        if(Impossible) {
            puts("Impossible");
        } else {
            for(int i = 0; i < m; ++i) {
                if(Cnt[i] != 1) {
                    for(int j = 0; j < n; ++j) {
                        if(Flag[i][j] == 0) {
                            Ans[i] = j;
                        }
                    }
                    if(i + 1 < m) {
                        if(Flag[i + 1][Ans[i]] == 0) {
                            Flag[i + 1][Ans[i]] = -1;
                        }
                    }
                }
                printf("%s:%s", Name[Ans[i]], strstr(Msg[i], ":") + 1);
            }
        }
    }
    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *