Submission #328247

#	Time	Username	Problem	Language	Result	Execution time	Memory
328247		daniel920712	Rope (JOI17_rope)	C++14	15 / 100	2563 ms	12268 KiB

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 (stderr)

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 / 15
• Subtask 2: 0 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20