Submission #31943

# Submission time Handle Problem Language Result Execution time Memory
31943 2017-09-17T14:36:48 Z Extazy Brunhilda’s Birthday (BOI13_brunhilda) C++14
7.77778 / 100
879 ms 65372 KB
#include <bits/stdc++.h>
#define endl '\n'

#define left aklhgjqghkqkj
#define right ajklvhajkvhajk
#define prev aioghajga
#define next ioyhjhfajasj
#define y0 iuadoghasdgj
#define y1 taklahgjkla
#define remainder pogjuakllhga
#define pow pajklgaklha
#define pow10 iopuioadjlgkah
#define div aljghajkghak
#define distance gkuftgjasgfjh
#define uppercase ifyhasjkhakjfas
#define tm aogqjgklqjgqklgjqlkq

//#define floor hjakjhaja
//#define time ashjlahjka
//#define double_t double

using namespace std;

const int N = 1<<17;
const int TO = (1e6);
const int INF = (1e9) + 7;

multiset < int > s;
vector < int > div[TO + 7];
int dp[TO + 7];
int sv[TO + 7];
int n,q;
int mx;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j,x;
    multiset < int >::iterator it;

    scanf("%d %d", &n, &q);
    for(i=1;i<=n;i++) {
        scanf("%d", &x);
        mx=max(mx,x);

        if(!div[x].empty()) continue;

        for(j=x;j<=TO;j+=x) {
            div[j].push_back(x);
        }
    }

    for(i=1;i<=TO;i++) {
        for(j=0;j<(int)(div[i].size());j++) {
            if(div[i][j]!=i) {
                if((it=s.find(dp[sv[div[i][j]]]))!=s.end()) {
                    s.erase(it);
                    //s.erase(s.find(dp[sv[div[i][j]]]));
                }
            }
        }
        
        if(i<mx) dp[i]=1;
        else if(s.empty()) dp[i]=INF;
        else dp[i]=1+(*s.begin());
        dp[i]=min(dp[i],INF);

        for(j=0;j<(int)(div[i].size());j++) {
            sv[div[i][j]]=i;
            s.insert(dp[i]);
        }

        while(s.size()>7) {
            it=s.end();
            --it;
            s.erase(it);
        }
    }

    while(q--) {
        scanf("%d", &x);
        if(dp[x]==INF) printf("oo\n");
        else printf("%d\n", dp[x]);
    }

    return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:41:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
brunhilda.cpp:43:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^
brunhilda.cpp:81:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^
# Verdict Execution time Memory Grader output
1 Correct 83 ms 38708 KB Output is correct
2 Incorrect 219 ms 56132 KB Output isn't correct
3 Correct 123 ms 52964 KB Output is correct
4 Incorrect 43 ms 35804 KB Output isn't correct
5 Incorrect 76 ms 41612 KB Output isn't correct
6 Correct 49 ms 38708 KB Output is correct
7 Correct 123 ms 52964 KB Output is correct
8 Correct 173 ms 56924 KB Output is correct
9 Incorrect 223 ms 59036 KB Output isn't correct
10 Incorrect 316 ms 59960 KB Output isn't correct
11 Incorrect 249 ms 55340 KB Output isn't correct
12 Correct 29 ms 35144 KB Output is correct
13 Incorrect 563 ms 62864 KB Output isn't correct
14 Correct 619 ms 62864 KB Output is correct
15 Incorrect 229 ms 55472 KB Output isn't correct
16 Incorrect 203 ms 56132 KB Output isn't correct
17 Incorrect 133 ms 41480 KB Output isn't correct
18 Incorrect 36 ms 35804 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 38576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 39 ms 39764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 833 ms 64976 KB Output isn't correct
4 Runtime error 179 ms 46496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 289 ms 59432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Incorrect 153 ms 52172 KB Output isn't correct
7 Runtime error 76 ms 38576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 186 ms 45044 KB Output isn't correct
9 Runtime error 333 ms 61676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 869 ms 64976 KB Output isn't correct
11 Runtime error 833 ms 63788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 343 ms 57320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 73 ms 41084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 183 ms 46496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 759 ms 62864 KB Output isn't correct
16 Runtime error 53 ms 39764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 716 ms 62336 KB Output isn't correct
18 Runtime error 353 ms 61808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 616 ms 63524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 783 ms 64316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 879 ms 64316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 356 ms 58376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 43 ms 39632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 623 ms 61412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 219 ms 56000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 679 ms 63524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 636 ms 63524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 406 ms 56132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 303 ms 52568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 526 ms 61016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Incorrect 826 ms 63128 KB Output isn't correct
14 Incorrect 436 ms 60620 KB Output isn't correct
15 Runtime error 559 ms 62468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 646 ms 62864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 563 ms 60884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 803 ms 64316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 96 ms 46496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 786 ms 64316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 433 ms 61940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 533 ms 64580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 166 ms 41744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 76 ms 39236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 393 ms 57584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 376 ms 58376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 583 ms 65372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Incorrect 159 ms 44516 KB Output isn't correct
29 Runtime error 363 ms 62864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 523 ms 61940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 143 ms 45440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 209 ms 48608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 39 ms 36728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 216 ms 56000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 116 ms 45176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 446 ms 64448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 39 ms 39632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 629 ms 61412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 106 ms 40952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 479 ms 60092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 213 ms 58244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Incorrect 733 ms 62996 KB Output isn't correct