2 条题解

  • 1
    @ 2022-8-29 9:43:29
    #include<bits/stdc++.h>
    using namespace std;
    #define il inline
    #define re register
    #define debug printf("Now is Line : %d\n",__LINE__)
    il int read()
    {
        re int x=0,f=1; re char c=getchar();
        while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
        while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
        return x*f;
    }
    #define maxn 10005
    int n,m,d[maxn],aa[2][maxn],vis[maxn],cnt,ans,match[maxn],to[maxn];
    bool dfs(int u)
    {
        for(re int i=0;i<2;++i)
        {
            int v=aa[i][u];
            if(vis[v]) continue;
            vis[v]=1;
            if(match[v]==-1||dfs(match[v])) return match[v]=u,to[u]=v,1;
        }
        return 0;
    }
    int main()
    {
        n=read();
        memset(match,-1,sizeof(match));
        for(re int i=0;i<n;++i) d[i]=read();
        for(re int i=0;i<n;++i)
        {
            int a=(i-d[i]+n)%n,b=(i+d[i])%n;
            if(a>b) swap(a,b);
            aa[0][i]=a,aa[1][i]=b;
        }
        for(re int i=n-1;~i;--i)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ++ans;
        }
        if(ans<n) return puts("No Answer"),0;
        for(re int i=0;i<n;++i) printf("%d ",to[i]);
        return 0;
    }
    
    • 0
      @ 2022-8-29 9:43:59
      #include<bits/stdc++.h>
      using namespace std;
      #define il inline
      #define re register
      #define debug printf("Now is Line : %d\n",__LINE__)
      il int read()
      {
          re int x=0,f=1; re char c=getchar();
          while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
          while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
          return x*f;
      }
      #define maxn 10005
      int n,m,d[maxn],aa[2][maxn],vis[maxn],cnt,ans,match[maxn],to[maxn];
      bool dfs(int u)
      {
          for(re int i=0;i<2;++i)
          {
              int v=aa[i][u];
              if(vis[v]) continue;
              vis[v]=1;
              if(match[v]==-1||dfs(match[v])) return match[v]=u,to[u]=v,1;
          }
          return 0;
      }
      int main()
      {
          n=read();
          memset(match,-1,sizeof(match));
          for(re int i=0;i<n;++i) d[i]=read();
          for(re int i=0;i<n;++i)
          {
              int a=(i-d[i]+n)%n,b=(i+d[i])%n;
              if(a>b) swap(a,b);
              aa[0][i]=a,aa[1][i]=b;
          }
          for(re int i=n-1;~i;--i)
          {
              memset(vis,0,sizeof(vis));
              if(dfs(i)) ++ans;
          }
          if(ans<n) return puts("No Answer"),0;
          for(re int i=0;i<n;++i) printf("%d ",to[i]);
          return 0;
      }
      
      • 1

      信息

      ID
      926
      时间
      1000ms
      内存
      125MiB
      难度
      6
      标签
      递交数
      5
      已通过
      3
      上传者