Submission #1438833


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
 
#define rep(i, n) for(int i = 0; i < (n); ++i)
 
using namespace std;

int n;
string s[10000];
string t;
int f[10000];
int b[10000];

void check(int p){
    if(t.size() == p){
        rep(i, n){
            if(f[i] == -1){
                f[i] = (s[i].size() == p);
            }
            
            if(b[i] == -1){
                b[i] = 1;
            }
        }
        return;
    }

    rep(i, n){
        if(f[i] == -1){
            if(s[i].size() == p){
                f[i] = 1;
            }
            else{
                if(s[i][p] == '?'){
                    if(t[p] != 'a'){
                        f[i] = 1;                   
                    }
                }
                else if(s[i][p] != t[p]){
                    f[i] = s[i][p] < t[p];
                }
            }
        }

        if(b[i] == -1){
            if(s[i].size() == p){
                b[i] = 0;
            }
            else{
                if(s[i][p] == '?'){
                    if(t[p] != 'z'){
                        b[i] = 1;                   
                    }
                }
                else if(s[i][p] != t[p]){
                    b[i] = s[i][p] > t[p];
                }
            }
        }
    }

    check(p + 1);
}

int main(){
    cin >> n;
    rep(i, n){
        cin >> s[i];
    }
    cin >> t;

    fill_n(f, n, -1);
    fill_n(b, n, -1);

    check(0);

    int p = 0;
    int q = 0;
    rep(i, n){
        if(f[i] && b[i]){
            ++q;
        }
        else if(f[i]){
            ++p;
        }
    }

    for(int i = 0; i <= q; ++i){
        if(i != 0){
            cout << ' ';
        }
        cout << p + i + 1;
    }
    cout << endl;
    return 0;
}

Submission Info

Submission Time
Task A - Atcoder Handles
User hipokaba
Language C++14 (GCC 5.4.1)
Score 250
Code Size 1865 Byte
Status AC
Exec Time 9 ms
Memory 1024 KB

Judge Result

Set Name Subtask1 Subtask2
Score / Max Score 130 / 130 120 / 120
Status
AC × 3
AC × 6
Set Name Test Cases
Subtask1 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt
Subtask2 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt
Case Name Status Exec Time Memory
sub1_in1.txt AC 1 ms 384 KB
sub1_in2.txt AC 2 ms 384 KB
sub1_in3.txt AC 2 ms 384 KB
sub2_in1.txt AC 1 ms 384 KB
sub2_in2.txt AC 5 ms 640 KB
sub2_in3.txt AC 9 ms 1024 KB