Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Results
History
2018-05-26 15:59:29
2018-05-26 15:57:38
2018-05-26 15:51:35
2018-05-26 15:50:50
2018-05-26 15:47:23
Task:Find a Word
Sender:HIIT AND RUN
Submission time:2018-05-26 15:59:29
Language:C++
Status:READY
Result:TIME LIMIT EXCEEDED

Test results

testverdicttime (s)
#1ACCEPTED0.02 / 1.00details
#2ACCEPTED0.01 / 1.00details
#3ACCEPTED0.01 / 1.00details
#4ACCEPTED0.01 / 1.00details
#5ACCEPTED0.01 / 1.00details
#6ACCEPTED0.01 / 1.00details
#7ACCEPTED0.01 / 1.00details
#8ACCEPTED0.01 / 1.00details
#9ACCEPTED0.01 / 1.00details
#10ACCEPTED0.01 / 1.00details
#11ACCEPTED0.01 / 1.00details
#12ACCEPTED0.02 / 1.00details
#13ACCEPTED0.02 / 1.00details
#14ACCEPTED0.01 / 1.00details
#15TIME LIMIT EXCEEDED-- / 1.00details
#16TIME LIMIT EXCEEDED-- / 1.00details

Compiler report

input/code.cpp: In function 'll has_duplicate(std::__cxx11::string&, ll, ll)':
input/code.cpp:38:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ((next_e.first == s) && (next_e.GETX == x) && (next_e.GETY == y)) {
                                     ~~~~~~~~~~~~^~~~
input/code.cpp:38:71: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ((next_e.first == s) && (next_e.GETX == x) && (next_e.GETY == y)) {
                                                           ~~~~~~~~~~~~^~~~

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long unsigned int ll;

char C[33][33];

#define GETX second.second.first
#define GETY second.first
#define GETCT second.second.second

set< pair< string, pair<int, pair<int,ll> > > > prevQ;
set< pair< string, pair<int, pair<int,ll> > > > nextQ;

ll n, k;

ll fact(ll x) {
    ll f = 1;
    for (ll i = 2; i <= x; ++i)
        f *= i;
    return f;
}

ll count_from(ll x, ll y) {
    ll nf = fact(n*2-2-x-y);
    ll df1 = fact(n-1-x);
    ll df2 = fact((n*2-2-x-y)-(n-1-x));
    
    return nf / (df1 * df2);
}

ll has_duplicate(string & s, ll x, ll y) {
    auto next_it = nextQ.upper_bound({s, {y ,{x, 0}}});
    
    if (next_it != nextQ.end()) {
        auto next_e = *next_it;
        if ((next_e.first == s) && (next_e.GETX == x) && (next_e.GETY == y)) {
            nextQ.erase(next_it);
            return next_e.GETCT;
        }
        return 0;
    }
    return 0;
}

int main () {
    cin >> n >> k;
    
    for (ll i = 0; i < n; ++i) {
        string line;
        cin >> line;
        
        for (ll j = 0; j < n; ++j) {
            C[i][j] = line[j];
        }
    }
    
    string e = "";
    e += C[0][0];
    prevQ.insert({e, {0 , {0, 1}}});
 
    while (true) {
        if (prevQ.begin()->first.size() == 2*n-1) break;
    
        string prev_prefix = "";
        ll cumulative = 0;
        
        vector < pair< string, pair<int, pair<int,ll> > > > eraselist;
        
        for (auto elem : prevQ) {
            string s = elem.first;
            ll y = elem.GETY;
            ll x = elem.GETX;
            ll ct = elem.GETCT;
            
            ll m = ct * count_from(x,y);
            
            
            
            //cout << s << " " << m << " " << cumulative << endl;
            
            if (prev_prefix.size() && s > prev_prefix && cumulative >= k) {
                //cout << "remove me" << endl;
                eraselist.push_back(elem);
            }
            
            prev_prefix = s;
            
            cumulative += m;
        }
        
        for (auto elem : eraselist)
            prevQ.erase(elem);
        
        
        while (prevQ.size()) {
            
            auto elem = *prevQ.begin();
            prevQ.erase(prevQ.begin());
            
            string s = elem.first;
            ll y = elem.GETY;
            ll x = elem.GETX;
            ll ct = elem.GETCT;
            
            
            //cout << s << " " << ct << endl;
            
            if (x < n-1) {
                ll newx = x+1;
                ll newy = y;
                
                //ll newct = count_from(newx, newy);
                string new_s = s + C[newy][newx];
                ll lol = has_duplicate(new_s, newx, newy);
                nextQ.insert({new_s, {newy, {newx, ct+lol}}});
            }
            
            if (y < n-1) {
                ll newx = x;
                ll newy = y+1;
                
                //ll newct = count_from(newx, newy);
                string new_s = s + C[newy][newx];
                ll lol = has_duplicate(new_s, newx, newy);
                nextQ.insert({new_s, {newy, {newx, ct+lol}}});
            }
        }
        
        swap(nextQ, prevQ);
    }
    
    /*
    for (auto elem : prevQ) {
        cout << elem.first << " " << elem.GETCT << endl;
    }
    */
    
    cout << prevQ.rbegin()->first << endl;
    
}

Test details

Test 1

Verdict: ACCEPTED

input
4 1
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 2

Verdict: ACCEPTED

input
4 2
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 3

Verdict: ACCEPTED

input
4 10
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 4

Verdict: ACCEPTED

input
4 19
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 5

Verdict: ACCEPTED

input
4 20
AAAA
AAAA
AAAA
AAAA
view   save

correct output
AAAAAAA
view   save

user output
AAAAAAA
view   save

Test 6

Verdict: ACCEPTED

input
4 1
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QEVHXCV
view   save

user output
QEVHXCV
view   save

Test 7

Verdict: ACCEPTED

input
4 2
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QEVHZCV
view   save

user output
QEVHZCV
view   save

Test 8

Verdict: ACCEPTED

input
4 10
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QEXRXCV
view   save

user output
QEXRXCV
view   save

Test 9

Verdict: ACCEPTED

input
4 19
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QNVJZCV
view   save

user output
QNVJZCV
view   save

Test 10

Verdict: ACCEPTED

input
4 20
QNJP
EVJU
XHZF
RXCV
view   save

correct output
QNVJZFV
view   save

user output
QNVJZFV
view   save

Test 11

Verdict: ACCEPTED

input
30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...
view   save

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

Test 12

Verdict: ACCEPTED

input
30 15033633249770520
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...
view   save

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

Test 13

Verdict: ACCEPTED

input
30 30067266499541040
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...
view   save

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

Test 14

Verdict: ACCEPTED

input
30 1
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
QHYOUWFHLJQDVTGVCSIVHNPKDWNJQC
GBUFNYPCWYNPQQMADZXQPYTAUETQSU
LURTALUCESXQWEFCOXPGXBFUIOMFBW
RJPAYRYBOCQKHOHRAWHJTITBTBTUQK
EMREBEZQUEFPCFEAYNTCYIBSMVIUPI
SCOSBRKAKZBPLLZPPOYCZRUTADFQEF
VKIJFVWGOCYMDCFXSEBAGJIRSKNYSK
FEVSYNRBXCOHWXGIRQOPNAIVYLXQOE
JNABESJIUMPKLSDJKBIGOSGCEJKNRN
SYROUHKKNTCYGDSSTYBQBYPOWUQIHS
YXZKTSAPWXLKLQGSNKTPGEAQIAHFMC
BAGQPHLNARILPPVQUYQOMTHOXNIKMZ
NLDRZQIWUYFGQXWCIQOCRXFUPKZWWY
AAROAOVNBBNVDZNZHOZGCHYAFTHHWD
DWCDSGBQZKLLXWHHWGXJQWNWENIZWZ
...
view   save

correct output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...
view   save

user output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...
view   save

Test 15

Verdict: TIME LIMIT EXCEEDED

input
30 15033633249770520
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
QHYOUWFHLJQDVTGVCSIVHNPKDWNJQC
GBUFNYPCWYNPQQMADZXQPYTAUETQSU
LURTALUCESXQWEFCOXPGXBFUIOMFBW
RJPAYRYBOCQKHOHRAWHJTITBTBTUQK
EMREBEZQUEFPCFEAYNTCYIBSMVIUPI
SCOSBRKAKZBPLLZPPOYCZRUTADFQEF
VKIJFVWGOCYMDCFXSEBAGJIRSKNYSK
FEVSYNRBXCOHWXGIRQOPNAIVYLXQOE
JNABESJIUMPKLSDJKBIGOSGCEJKNRN
SYROUHKKNTCYGDSSTYBQBYPOWUQIHS
YXZKTSAPWXLKLQGSNKTPGEAQIAHFMC
BAGQPHLNARILPPVQUYQOMTHOXNIKMZ
NLDRZQIWUYFGQXWCIQOCRXFUPKZWWY
AAROAOVNBBNVDZNZHOZGCHYAFTHHWD
DWCDSGBQZKLLXWHHWGXJQWNWENIZWZ
...
view   save

correct output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...
view   save

user output
(no output)
view   save

Test 16

Verdict: TIME LIMIT EXCEEDED

input
30 30067266499541040
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
QHYOUWFHLJQDVTGVCSIVHNPKDWNJQC
GBUFNYPCWYNPQQMADZXQPYTAUETQSU
LURTALUCESXQWEFCOXPGXBFUIOMFBW
RJPAYRYBOCQKHOHRAWHJTITBTBTUQK
EMREBEZQUEFPCFEAYNTCYIBSMVIUPI
SCOSBRKAKZBPLLZPPOYCZRUTADFQEF
VKIJFVWGOCYMDCFXSEBAGJIRSKNYSK
FEVSYNRBXCOHWXGIRQOPNAIVYLXQOE
JNABESJIUMPKLSDJKBIGOSGCEJKNRN
SYROUHKKNTCYGDSSTYBQBYPOWUQIHS
YXZKTSAPWXLKLQGSNKTPGEAQIAHFMC
BAGQPHLNARILPPVQUYQOMTHOXNIKMZ
NLDRZQIWUYFGQXWCIQOCRXFUPKZWWY
AAROAOVNBBNVDZNZHOZGCHYAFTHHWD
DWCDSGBQZKLLXWHHWGXJQWNWENIZWZ
...
view   save

correct output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...
view   save

user output
(no output)
view   save