Submission #159264

#	Time	Username	Problem	Language	Result	Execution time	Memory
159264		ppnxblstr	Alternating Current (BOI18_alternating)	C++14	19 / 100	61 ms	6392 KiB

alternating

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int i,j,n,m,l,r,t=0,y,z,s=0,u,v,a=-1,b,tail,htail,cmm,full;
  scanf("%d %d\n",&n,&m);

  int reci[m]={},recf[m]={};
  int ans[m]={};
  int count[n]={};
  int alert[n]={};
  int st[n]={},en[n]={};
  int pin[n]={};
  int pinsort[m]={};
  for(i=0;i<n;i++)
  {
    pin[i]--;
  }
  for(i=0;i<m;i++)
  {
    scanf("%d %d",&l,&r);
    st[l-1]++;
    en[r-1]++;
    reci[i]=l-1;
    if(l>r)
    {count[n-1]++;}
    else if(r==n)
    {count[n-1]++;}
    recf[i]=r-1;
    if(pin[r-1]==-1)
    {pin[r-1]=i;s++;}
  }
  for(i=0;i<n-1;i++)
  {
    if(i==0)
    {
      count[0]=count[n-1]+st[0]-en[n-1];
    }
    else
    {
      count[i]=count[i-1]+st[i]-en[i-1];
    }
  }
  for(i=0;i<n;i++)
  {
    if(count[i]<2)
    {printf("impossible");return 0;}
    if(count[i]==2)
    {alert[t]=i;t++;}
  }
  y=0;
  z=0;
  if(t!=0)
  {
    for(i=alert[t-1]+1;i<=n+alert[t-1];i++)
    {
      j=i%n;
      z+=st[j];
      if(z>=2)
      {break;}
      if(j==alert[y])
      {
        y++;z=0;
      }
    }
  }
  int hi[s]={};
  j=0;
  i=0;
  while(j<s)
  {
    if(pin[i]!=-1)
    {
      hi[j]=pin[i];
      j++;
    }
    i++;
  }
  int gi[s]={};
  int ad[s]={};
  int rehi[n]={};
  for(i=0;i<s;i++)
  {
    rehi[recf[hi[i]]]=i;
  }
  gi[0]=0;
  for(i=1;i<s;i++)
  {
    gi[i]=gi[i-1]+en[recf[hi[i-1]]];
  }
  for(i=0;i<m;i++)
  {
    u=rehi[recf[i]];
    v=gi[u]+ad[u];
    pinsort[v]=i;
    ad[u]++;
  }
  if(t==0)
  {
    cmm=n-1;
    int mst=n,mnd=n;
    for(i=0;i<m;i++)
    {
      if(recf[i]==n-1||recf[i]<reci[i])
      {
        if(reci[i]<mst)
        {
          b=a;
          a=i;
          mnd=mst;
          mst=recf[i];
        }
        else if(reci[i]<mnd)
        {
          b=i;
          mnd=recf[i];
        }
      }
    }
  }
  else if(y==t)
  {
    cmm=alert[0];
    for(i=0;i<m;i++)
    {
      if(reci[i]<=alert[0]&&recf[i]>=alert[0]||reci[i]>recf[i]&&(reci[i]<=alert[0]||recf[i]>=alert[0]))
      {
        if(a==-1)
        {
          a=i;
        }
        else
        {
          b=i;
        }
      }
    }
    for(tail=t-1;tail>0;tail--)
    {
      if((alert[tail]<reci[a]||reci[a]<=alert[0])&&(alert[tail]<reci[b]||reci[b]<=alert[0]))
      {
        tail++;
        break;
      }
    }
    if(alert[tail]>=reci[a]&&reci[a]>alert[0])
    {
      htail=1;
    }
    else
    {
      htail=2;
    }
  }
  else
  {
    cmm=alert[y];
    for(i=0;i<m;i++)
    {
      if(reci[i]<=alert[y]&&recf[i]>=alert[y]||reci[i]>recf[i]&&(reci[i]<=alert[y]||recf[i]>=alert[y]))
      {
        if(a==-1)
        {
          a=i;
        }
        else
        {
          b=i;
        }
      }
    }
  }
  ans[a]=1;
  ans[b]=2;
  int in2,fi2,in1,fi1,di2,di1,dic2,dic1,i1,i2,ff1,ff2;
  in2=reci[b];
  in1=reci[a];
  fi2=recf[b];
  fi1=recf[a];
  di2=(fi2-in2+n+1)%n;
  di1=(fi1-in1+n+1)%n;
  dic2=di2;
  dic1=di1;
  i1=0;
  i2=0;
  if(di1==0)
  {
    for(i=0;i<m;i++)
    {
      printf("%d",ans[i]%2);
    }
    return 0;
  }
  if(di2==0)
  {
    for(i=0;i<m;i++)
    {
      printf("%d",ans[i]/2);
    }
    return 0;
  }
  while(true)
  {
    if((fi2-cmm+n)%n>=(fi1-cmm+n)%n)
    {
      i1=(i1+1)%m;
      ff1=(fi1+1)%n;
      if(ans[pinsort[i1]]!=0)
      {
        continue;
      }
      if(ff1>=reci[pinsort[i1]]&&ff1<=recf[pinsort[i1]]||reci[pinsort[i1]]>recf[pinsort[i1]]&&(reci[pinsort[i1]]<=ff1||recf[pinsort[i1]]>=ff1))
      {
        ans[pinsort[i1]]=1;
        fi1=recf[pinsort[i1]];
        di1=(fi1-in1+n+1)%n;
        if(di1<=dic1)
        {
          full=1;
          break;
        }
        dic1=di1;
      }

    }
    else
    {
      i2=(i2+1)%m;
      ff2=(fi2+1)%n;
      if(ans[pinsort[i2]]!=0)
      {
        continue;
      }
      if(ff2>=reci[pinsort[i2]]&&ff2<=recf[pinsort[i2]]||reci[pinsort[i2]]>recf[pinsort[i2]]&&(reci[pinsort[i2]]<=ff2||recf[pinsort[i2]]>=ff2))
      {
        ans[pinsort[i2]]=2;
        fi2=recf[pinsort[i2]];
        di2=(fi2-in2+n+1)%n;
        if(di2<=dic2)
        {
          full=2;
          break;
        }
        dic2=di2;
      }
    }
  }
  if(t!=0&&y==t)
  {
    int lch1=-1,lch2;
    for(i=0;i<m;i++)
      {
        if(reci[i]<=alert[tail]&&recf[i]>=alert[tail]||reci[i]>recf[i]&&(reci[i]<=alert[tail]||recf[i]>=alert[tail]))
        {
          if(lch1!=-1)
          {
            lch2=i;
            break;
          }
          lch1=i;
        }
      }
    if(ans[lch1]==ans[lch2])
    {
      printf("impossible");
    }
  }
  if(full==1)
  {
    for(i=0;i<m;i++)
    {
      printf("%d",ans[i]%2);
    }
    return 0;
  }
  if(full==2)
  {
    for(i=0;i<m;i++)
    {
      printf("%d",ans[i]/2);
    }
    return 0;
  }
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:126:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if(reci[i]<=alert[0]&&recf[i]>=alert[0]||reci[i]>recf[i]&&(reci[i]<=alert[0]||recf[i]>=alert[0]))
          ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
alternating.cpp:160:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if(reci[i]<=alert[y]&&recf[i]>=alert[y]||reci[i]>recf[i]&&(reci[i]<=alert[y]||recf[i]>=alert[y]))
          ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
alternating.cpp:212:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if(ff1>=reci[pinsort[i1]]&&ff1<=recf[pinsort[i1]]||reci[pinsort[i1]]>recf[pinsort[i1]]&&(reci[pinsort[i1]]<=ff1||recf[pinsort[i1]]>=ff1))
          ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp:234:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if(ff2>=reci[pinsort[i2]]&&ff2<=recf[pinsort[i2]]||reci[pinsort[i2]]>recf[pinsort[i2]]&&(reci[pinsort[i2]]<=ff2||recf[pinsort[i2]]>=ff2))
          ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp:253:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if(reci[i]<=alert[tail]&&recf[i]>=alert[tail]||reci[i]>recf[i]&&(reci[i]<=alert[tail]||recf[i]>=alert[tail]))
            ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
alternating.cpp:5:47: warning: variable 'htail' set but not used [-Wunused-but-set-variable]
   int i,j,n,m,l,r,t=0,y,z,s=0,u,v,a=-1,b,tail,htail,cmm,full;
                                               ^~~~~
alternating.cpp:6:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d\n",&n,&m);
   ~~~~~^~~~~~~~~~~~~~~~~
alternating.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&l,&r);
     ~~~~~^~~~~~~~~~~~~~~
alternating.cpp:263:27: warning: 'lch2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(ans[lch1]==ans[lch2])
                   ~~~~~~~~^
alternating.cpp:253:31: warning: 'tail' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(reci[i]<=alert[tail]&&recf[i]>=alert[tail]||reci[i]>recf[i]&&(reci[i]<=alert[tail]||recf[i]>=alert[tail]))
                     ~~~~~~~~~~^
alternating.cpp:176:6: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   in2=reci[b];
   ~~~^~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26