oj.uz

Submission #334929

# Submission time Handle Problem Language Result Execution time Memory
334929 2020-12-10T10:31:17 Z beksultan04 Nice sequence (IZhO18_sequence) C++14
43 / 100
 113 ms 3172 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define OK puts("OK");
#define fr first
#define sc second
#define ret return
#define scan1(a) scanf("%lld",&a);
#define scan2(a,b) scanf("%lld %lld",&a, &b);
#define scan3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define pb push_back
#define endi puts("");
const int N = 2e5+12,INF=1e9+7;
int sz,vis[N],pref[N],m,n;
vector <int> v;
void dfs(int x){
    vis[x]=1;
    if (x-m >= 0 && !vis[x-m]){
        dfs(x-m);
    }
    if (x+n<=sz && !vis[x+n]){
        dfs(x+n);
    }
    v.pb(x);
}

bool is(int x){
    sz = x;
    v.clear();
    int i;
    for (i=0;i<=sz;++i)
        vis[i]=0;
    for (i=0;i<=sz;++i)
        if (!vis[i])dfs(i);
    for (i=0;i<v.size();++i){
        pref[v[i]]=i;
    }
    for (i=0;i<=sz;++i){
        if (i-m >= 0 && pref[i] <= pref[i-m])ret 0;
        if (i+n <= sz && pref[i] <= pref[i+n])ret 0;
    }
    ret 1;
}

main(){
    int t;
    scan1(t)
    while (t--){
        int i,j;
        scan2(n,m)
        int l=0,r=40000;
        while (l<r){
            int m = (l+r+1)>>1;
            if (is(m)){
                l=m;
            }
            else r = m-1;
        }
        is(l);
        cout <<l<<"\n";
        for (i=1;i<=l;++i){
            cout <<pref[i]-pref[i-1]<<" ";
        }
        endi
    }
}

Compilation message

sequence.cpp: In function 'bool is(long long int)':
sequence.cpp:37:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (i=0;i<v.size();++i){
      |              ~^~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:47:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      |      ^
sequence.cpp: In function 'int main()':
sequence.cpp:51:15: warning: unused variable 'j' [-Wunused-variable]
   51 |         int i,j;
      |               ^
sequence.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 | #define scan1(a) scanf("%lld",&a);
      |                  ~~~~~^~~~~~~~~~~
sequence.cpp:49:5: note: in expansion of macro 'scan1'
   49 |     scan1(t)
      |     ^~~~~
sequence.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 | #define scan2(a,b) scanf("%lld %lld",&a, &b);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~
sequence.cpp:52:9: note: in expansion of macro 'scan2'
   52 |         scan2(n,m)
      |         ^~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1516 KB Ok
2 Correct 6 ms 1516 KB Ok
3 Correct 7 ms 1000 KB Ok
4 Correct 7 ms 1128 KB Ok
5 Correct 6 ms 1000 KB Ok
6 Correct 6 ms 1128 KB Ok
7 Correct 6 ms 1020 KB Ok
8 Correct 6 ms 1128 KB Ok
9 Correct 6 ms 1000 KB Ok
10 Correct 40 ms 1256 KB Ok
11 Correct 7 ms 1000 KB Ok
12 Correct 6 ms 1000 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1512 KB Ok
2 Correct 7 ms 1512 KB Ok
3 Correct 8 ms 1512 KB Ok
4 Correct 7 ms 1512 KB Ok
5 Correct 6 ms 1512 KB Ok
6 Correct 11 ms 1640 KB Ok
7 Correct 30 ms 1896 KB Ok
8 Correct 17 ms 1768 KB Ok
9 Correct 34 ms 2052 KB Ok
10 Correct 23 ms 1768 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1516 KB Ok
2 Correct 6 ms 1516 KB Ok
3 Correct 7 ms 1512 KB Ok
4 Correct 7 ms 1516 KB Ok
5 Correct 7 ms 1516 KB Ok
6 Correct 7 ms 1512 KB Ok
7 Correct 7 ms 1516 KB Ok
8 Correct 7 ms 1516 KB Ok
9 Correct 7 ms 1512 KB Ok
10 Correct 7 ms 1512 KB Ok
11 Correct 9 ms 1512 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1644 KB Ok
2 Correct 9 ms 1516 KB Ok
3 Correct 8 ms 1516 KB Ok
4 Correct 8 ms 1516 KB Ok
5 Correct 8 ms 1536 KB Ok
6 Incorrect 106 ms 3172 KB Jury has the better answer : jans = 166803, pans = 40000
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1516 KB Ok
2 Correct 6 ms 1516 KB Ok
3 Correct 7 ms 1000 KB Ok
4 Correct 7 ms 1128 KB Ok
5 Correct 6 ms 1000 KB Ok
6 Correct 6 ms 1128 KB Ok
7 Correct 6 ms 1020 KB Ok
8 Correct 6 ms 1128 KB Ok
9 Correct 6 ms 1000 KB Ok
10 Correct 40 ms 1256 KB Ok
11 Correct 7 ms 1000 KB Ok
12 Correct 6 ms 1000 KB Ok
13 Correct 3 ms 1516 KB Ok
14 Correct 6 ms 1516 KB Ok
15 Correct 7 ms 1512 KB Ok
16 Correct 7 ms 1516 KB Ok
17 Correct 7 ms 1516 KB Ok
18 Correct 7 ms 1512 KB Ok
19 Correct 7 ms 1516 KB Ok
20 Correct 7 ms 1516 KB Ok
21 Correct 7 ms 1512 KB Ok
22 Correct 7 ms 1512 KB Ok
23 Correct 9 ms 1512 KB Ok
24 Correct 10 ms 1000 KB Ok
25 Correct 10 ms 1020 KB Ok
26 Correct 11 ms 1000 KB Ok
27 Correct 10 ms 1000 KB Ok
28 Correct 9 ms 1000 KB Ok
29 Correct 10 ms 1128 KB Ok
30 Correct 11 ms 1020 KB Ok
31 Correct 11 ms 1000 KB Ok
32 Correct 11 ms 1000 KB Ok
33 Correct 10 ms 1000 KB Ok
34 Correct 18 ms 1640 KB Ok
35 Correct 18 ms 1640 KB Ok
36 Correct 18 ms 1640 KB Ok
37 Correct 18 ms 1640 KB Ok
38 Correct 18 ms 1640 KB Ok
39 Correct 18 ms 1640 KB Ok
40 Correct 20 ms 1640 KB Ok
41 Correct 19 ms 1768 KB Ok
42 Correct 19 ms 1640 KB Ok
43 Correct 19 ms 1640 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1516 KB Ok
2 Correct 6 ms 1516 KB Ok
3 Correct 7 ms 1000 KB Ok
4 Correct 7 ms 1128 KB Ok
5 Correct 6 ms 1000 KB Ok
6 Correct 6 ms 1128 KB Ok
7 Correct 6 ms 1020 KB Ok
8 Correct 6 ms 1128 KB Ok
9 Correct 6 ms 1000 KB Ok
10 Correct 40 ms 1256 KB Ok
11 Correct 7 ms 1000 KB Ok
12 Correct 6 ms 1000 KB Ok
13 Correct 7 ms 1512 KB Ok
14 Correct 7 ms 1512 KB Ok
15 Correct 8 ms 1512 KB Ok
16 Correct 7 ms 1512 KB Ok
17 Correct 6 ms 1512 KB Ok
18 Correct 11 ms 1640 KB Ok
19 Correct 30 ms 1896 KB Ok
20 Correct 17 ms 1768 KB Ok
21 Correct 34 ms 2052 KB Ok
22 Correct 23 ms 1768 KB Ok
23 Correct 3 ms 1516 KB Ok
24 Correct 6 ms 1516 KB Ok
25 Correct 7 ms 1512 KB Ok
26 Correct 7 ms 1516 KB Ok
27 Correct 7 ms 1516 KB Ok
28 Correct 7 ms 1512 KB Ok
29 Correct 7 ms 1516 KB Ok
30 Correct 7 ms 1516 KB Ok
31 Correct 7 ms 1512 KB Ok
32 Correct 7 ms 1512 KB Ok
33 Correct 9 ms 1512 KB Ok
34 Correct 10 ms 1000 KB Ok
35 Correct 10 ms 1020 KB Ok
36 Correct 11 ms 1000 KB Ok
37 Correct 10 ms 1000 KB Ok
38 Correct 9 ms 1000 KB Ok
39 Correct 10 ms 1128 KB Ok
40 Correct 11 ms 1020 KB Ok
41 Correct 11 ms 1000 KB Ok
42 Correct 11 ms 1000 KB Ok
43 Correct 10 ms 1000 KB Ok
44 Correct 18 ms 1640 KB Ok
45 Correct 18 ms 1640 KB Ok
46 Correct 18 ms 1640 KB Ok
47 Correct 18 ms 1640 KB Ok
48 Correct 18 ms 1640 KB Ok
49 Correct 18 ms 1640 KB Ok
50 Correct 20 ms 1640 KB Ok
51 Correct 19 ms 1768 KB Ok
52 Correct 19 ms 1640 KB Ok
53 Correct 19 ms 1640 KB Ok
54 Incorrect 113 ms 2148 KB Jury has the better answer : jans = 82899, pans = 40000
55 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1516 KB Ok
2 Correct 6 ms 1516 KB Ok
3 Correct 7 ms 1000 KB Ok
4 Correct 7 ms 1128 KB Ok
5 Correct 6 ms 1000 KB Ok
6 Correct 6 ms 1128 KB Ok
7 Correct 6 ms 1020 KB Ok
8 Correct 6 ms 1128 KB Ok
9 Correct 6 ms 1000 KB Ok
10 Correct 40 ms 1256 KB Ok
11 Correct 7 ms 1000 KB Ok
12 Correct 6 ms 1000 KB Ok
13 Correct 7 ms 1512 KB Ok
14 Correct 7 ms 1512 KB Ok
15 Correct 8 ms 1512 KB Ok
16 Correct 7 ms 1512 KB Ok
17 Correct 6 ms 1512 KB Ok
18 Correct 11 ms 1640 KB Ok
19 Correct 30 ms 1896 KB Ok
20 Correct 17 ms 1768 KB Ok
21 Correct 34 ms 2052 KB Ok
22 Correct 23 ms 1768 KB Ok
23 Correct 3 ms 1516 KB Ok
24 Correct 6 ms 1516 KB Ok
25 Correct 7 ms 1512 KB Ok
26 Correct 7 ms 1516 KB Ok
27 Correct 7 ms 1516 KB Ok
28 Correct 7 ms 1512 KB Ok
29 Correct 7 ms 1516 KB Ok
30 Correct 7 ms 1516 KB Ok
31 Correct 7 ms 1512 KB Ok
32 Correct 7 ms 1512 KB Ok
33 Correct 9 ms 1512 KB Ok
34 Correct 8 ms 1644 KB Ok
35 Correct 9 ms 1516 KB Ok
36 Correct 8 ms 1516 KB Ok
37 Correct 8 ms 1516 KB Ok
38 Correct 8 ms 1536 KB Ok
39 Incorrect 106 ms 3172 KB Jury has the better answer : jans = 166803, pans = 40000
40 Halted 0 ms 0 KB -