Submission #328247

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
328247	2020-11-16T01:41:08 Z	daniel920712	Rope (JOI17_rope)	C++14	15 / 100	2500 ms	12268 KB

rope

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <map>
#include <utility>
#include <algorithm>
#include <stack>
using namespace std;
int all[1000005];
int temp[1000005];
int ans[1000005];
deque < int > how;
int N,M;
void F(int x,int y,int here,int con)
{
    int now=0,ok=1,i;
    if(here==N)
    {
        how.clear();
        for(i=0;i<N;i++)
        {
            if(i&&temp[i]!=temp[i-1])
            {
                how.push_back(now);
                now=1;
            }
            else now++;
        }
        how.push_back(now);
        how.pop_back();
        if(!how.empty()) how.pop_front();
        while(!how.empty())
        {
            if(how.front()%2) ok=0;
            how.pop_front();
        }
        if(ok)
        {
            ans[x]=min(ans[x],con);
            ans[y]=min(ans[y],con);
        }
    }
    else
    {
        if(all[here]!=x&&all[here]!=y)
        {
            temp[here]=x;
            F(x,y,here+1,con+1);
            temp[here]=y;
            F(x,y,here+1,con+1);
        }
        else if(all[here]==x)
        {
            temp[here]=x;
            F(x,y,here+1,con);
            temp[here]=y;
            F(x,y,here+1,con+1);
        }
        else
        {
            temp[here]=x;
            F(x,y,here+1,con+1);
            temp[here]=y;
            F(x,y,here+1,con);
        }
    }
}
int main()
{
    int i,j;
    scanf("%d %d",&N,&M);
    for(i=0;i<N;i++) scanf("%d",&all[i]);
    for(i=1;i<=M;i++) ans[i]=1e9;
    for(i=1;i<=M;i++) for(j=i;j<=M;j++) F(i,j,0,0);

    for(i=1;i<=M;i++) printf("%d\n",ans[i]);
	return 0;
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
rope.cpp:74:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     for(i=0;i<N;i++) scanf("%d",&all[i]);
      |                      ~~~~~^~~~~~~~~~~~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	364 KB	Output is correct
2	Correct	16 ms	384 KB	Output is correct
3	Correct	34 ms	364 KB	Output is correct
4	Correct	28 ms	492 KB	Output is correct
5	Correct	8 ms	364 KB	Output is correct
6	Correct	35 ms	364 KB	Output is correct
7	Correct	59 ms	384 KB	Output is correct
8	Correct	74 ms	384 KB	Output is correct
9	Correct	56 ms	492 KB	Output is correct
10	Correct	39 ms	364 KB	Output is correct
11	Correct	5 ms	364 KB	Output is correct
12	Correct	4 ms	364 KB	Output is correct
13	Correct	3 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	3 ms	364 KB	Output is correct
18	Correct	2 ms	364 KB	Output is correct
19	Correct	2 ms	364 KB	Output is correct
20	Correct	2 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	0 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct

Subtask #2

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	364 KB	Output is correct
2	Correct	16 ms	384 KB	Output is correct
3	Correct	34 ms	364 KB	Output is correct
4	Correct	28 ms	492 KB	Output is correct
5	Correct	8 ms	364 KB	Output is correct
6	Correct	35 ms	364 KB	Output is correct
7	Correct	59 ms	384 KB	Output is correct
8	Correct	74 ms	384 KB	Output is correct
9	Correct	56 ms	492 KB	Output is correct
10	Correct	39 ms	364 KB	Output is correct
11	Correct	5 ms	364 KB	Output is correct
12	Correct	4 ms	364 KB	Output is correct
13	Correct	3 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	3 ms	364 KB	Output is correct
18	Correct	2 ms	364 KB	Output is correct
19	Correct	2 ms	364 KB	Output is correct
20	Correct	2 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	0 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Execution timed out	2563 ms	12268 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	364 KB	Output is correct
2	Correct	16 ms	384 KB	Output is correct
3	Correct	34 ms	364 KB	Output is correct
4	Correct	28 ms	492 KB	Output is correct
5	Correct	8 ms	364 KB	Output is correct
6	Correct	35 ms	364 KB	Output is correct
7	Correct	59 ms	384 KB	Output is correct
8	Correct	74 ms	384 KB	Output is correct
9	Correct	56 ms	492 KB	Output is correct
10	Correct	39 ms	364 KB	Output is correct
11	Correct	5 ms	364 KB	Output is correct
12	Correct	4 ms	364 KB	Output is correct
13	Correct	3 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	3 ms	364 KB	Output is correct
18	Correct	2 ms	364 KB	Output is correct
19	Correct	2 ms	364 KB	Output is correct
20	Correct	2 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	0 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Execution timed out	2563 ms	12268 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	364 KB	Output is correct
2	Correct	16 ms	384 KB	Output is correct
3	Correct	34 ms	364 KB	Output is correct
4	Correct	28 ms	492 KB	Output is correct
5	Correct	8 ms	364 KB	Output is correct
6	Correct	35 ms	364 KB	Output is correct
7	Correct	59 ms	384 KB	Output is correct
8	Correct	74 ms	384 KB	Output is correct
9	Correct	56 ms	492 KB	Output is correct
10	Correct	39 ms	364 KB	Output is correct
11	Correct	5 ms	364 KB	Output is correct
12	Correct	4 ms	364 KB	Output is correct
13	Correct	3 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	3 ms	364 KB	Output is correct
18	Correct	2 ms	364 KB	Output is correct
19	Correct	2 ms	364 KB	Output is correct
20	Correct	2 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	0 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Execution timed out	2563 ms	12268 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	364 KB	Output is correct
2	Correct	16 ms	384 KB	Output is correct
3	Correct	34 ms	364 KB	Output is correct
4	Correct	28 ms	492 KB	Output is correct
5	Correct	8 ms	364 KB	Output is correct
6	Correct	35 ms	364 KB	Output is correct
7	Correct	59 ms	384 KB	Output is correct
8	Correct	74 ms	384 KB	Output is correct
9	Correct	56 ms	492 KB	Output is correct
10	Correct	39 ms	364 KB	Output is correct
11	Correct	5 ms	364 KB	Output is correct
12	Correct	4 ms	364 KB	Output is correct
13	Correct	3 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	3 ms	364 KB	Output is correct
18	Correct	2 ms	364 KB	Output is correct
19	Correct	2 ms	364 KB	Output is correct
20	Correct	2 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	0 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Execution timed out	2563 ms	12268 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-