oj.uz

Submission #31941

# Submission time Handle Problem Language Result Execution time Memory
31941 2017-09-17T14:16:54 Z Extazy Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 1000 ms 68276 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;

    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) {
                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(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:40: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:42:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^
brunhilda.cpp:71:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 38708 KB Output is correct
2 Correct 266 ms 56132 KB Output is correct
3 Correct 143 ms 52964 KB Output is correct
4 Correct 53 ms 35804 KB Output is correct
5 Correct 86 ms 41612 KB Output is correct
6 Correct 69 ms 38708 KB Output is correct
7 Correct 153 ms 52964 KB Output is correct
8 Correct 203 ms 56924 KB Output is correct
9 Correct 283 ms 59036 KB Output is correct
10 Correct 349 ms 59960 KB Output is correct
11 Correct 296 ms 55340 KB Output is correct
12 Correct 36 ms 35144 KB Output is correct
13 Correct 806 ms 62864 KB Output is correct
14 Correct 843 ms 62864 KB Output is correct
15 Correct 286 ms 55472 KB Output is correct
16 Correct 249 ms 56132 KB Output is correct
17 Correct 169 ms 41480 KB Output is correct
18 Correct 53 ms 35804 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 39104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 46 ms 39764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Execution timed out 1000 ms 68276 KB Execution timed out
4 Incorrect 273 ms 46628 KB Output isn't correct
5 Runtime error 313 ms 59432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Incorrect 226 ms 52304 KB Output isn't correct
7 Runtime error 99 ms 39104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 223 ms 45044 KB Output isn't correct
9 Runtime error 346 ms 61676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Execution timed out 1000 ms 68276 KB Execution timed out
11 Execution timed out 1000 ms 65636 KB Execution timed out
12 Runtime error 456 ms 57452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 103 ms 41216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 269 ms 46628 KB Output isn't correct
15 Execution timed out 1000 ms 64844 KB Execution timed out
16 Runtime error 43 ms 39764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 913 ms 62600 KB Output isn't correct
18 Runtime error 329 ms 61808 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 899 ms 65900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Execution timed out 1000 ms 66824 KB Execution timed out
3 Execution timed out 1000 ms 66692 KB Execution timed out
4 Runtime error 539 ms 58508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 49 ms 39632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 793 ms 61676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 239 ms 56000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 909 ms 65900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 976 ms 65900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 539 ms 56396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 383 ms 52832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 813 ms 61412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Execution timed out 1000 ms 64448 KB Execution timed out
14 Incorrect 503 ms 60620 KB Output isn't correct
15 Runtime error 893 ms 62732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Execution timed out 1000 ms 63260 KB Execution timed out
17 Runtime error 819 ms 62996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Execution timed out 1000 ms 66824 KB Execution timed out
19 Runtime error 159 ms 46760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Execution timed out 1000 ms 66692 KB Execution timed out
21 Runtime error 549 ms 61940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 516 ms 64580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 176 ms 43196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 103 ms 39236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 599 ms 57716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 533 ms 58508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 619 ms 65372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Incorrect 203 ms 44516 KB Output isn't correct
29 Runtime error 399 ms 62864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 703 ms 65240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 179 ms 45704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 269 ms 48740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 49 ms 36860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 233 ms 56000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Incorrect 219 ms 45308 KB Output isn't correct
36 Runtime error 483 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 819 ms 61676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 126 ms 40952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 629 ms 60488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 203 ms 58244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 839 ms 63128 KB Execution killed with signal 11 (could be triggered by violating memory limits)