传送门

根据公式xjb推一下,然后就可以连边。

考虑到字典序最小,和匈牙利算法的实现过程,要倒序匹配。

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 40001 using namespace std; int n, cnt;
int head[N], to[N], nex[N], belong[N], a[N];
bool vis[N];
vector <int> vec; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline bool check(int x, int y, int d)
{
return 0 <= x && x < n && min(abs(x - y), n - abs(x - y)) == d;
} inline void add(int x, int y)
{
to[cnt] = y;
nex[cnt] = head[x];
head[x] = cnt++;
} inline bool dfs(int u)
{
int i, v;
for(i = head[u]; ~i; i = nex[i])
{
v = to[i];
if(!vis[v])
{
vis[v] = 1;
if(!belong[v] || dfs(belong[v]))
{
belong[v] = u;
return 1;
}
}
}
return 0;
} inline bool solve()
{
int i, ans = 0;
for(i = n - 1; i >= 0; i--)
{
memset(vis, 0, sizeof(vis));
ans += dfs(i);
}
return ans == n;
} int main()
{
int i, j, x, d;
n = read();
memset(head, -1, sizeof(head));
for(i = 0; i < n; i++)
{
d = read();
vec.clear();
x = d + i;
if(check(x, i, d)) vec.push_back(x);
x = n - d + i;
if(check(x, i, d)) vec.push_back(x);
x = i - d;
if(check(x, i, d)) vec.push_back(x);
x = i - n + d;
if(check(x, i, d)) vec.push_back(x);
sort(vec.begin(), vec.end());
if(vec.size()) for(j = vec.size() - 1; j >= 0; j--) add(i, vec[j]);
}
if(!solve()) puts("No Answer");
else
{
for(i = 0; i < n; i++) a[belong[i]] = i;
for(i = 0; i < n; i++) printf("%d ", a[i]);
}
return 0;
}

  

最新文章

  1. php实现设计模式之 备忘录模式
  2. R语言之词云:wordcloud&amp;wordcloud2安装及参数说明
  3. java之数组
  4. 年前辞职-WCF入门学习(4)
  5. JAX-WS(一)之使用wsgen从Java创建简单的WebService
  6. mysql长连接和短连接的问题 转
  7. ylbtech-数据库设计与优化-对作为复选框/单选列表的集合表的设计
  8. Android如何在ListView中嵌套ListView
  9. C语言——打印魔方阵(每一行,每一列,对角线之和相等)
  10. codeigniter nginx rewrite规则配置【转】
  11. [置顶] chinayaosir近10年来所阅读的世界著名IT书籍-图文并茂
  12. WCF技术剖析之三:如何进行基于非HTTP的IIS服务寄宿
  13. Openjudge-NOI题库-简单算术表达式求值
  14. STM32串口寄存器操作(转)
  15. 【转载】BAT 批处理脚本教程
  16. python 输出颜色的与样式的方法
  17. Java并发系列[7]----CountDownLatch源码分析
  18. [十二省联考2019]D1T1异或粽子
  19. CSS 实现自动换行、强制换行、强制不换行的属性
  20. -1-0 Java 简介 java是什么 java简单介绍

热门文章

  1. 香港城大:首创3D打印磁控微型机器人技术推动人体送药研究发展
  2. GitHub和码云的简单使用
  3. javaweb基础(12)_session详解
  4. Factorialize a Number-freecodecamp算法题目
  5. Linux - NodeJS安装
  6. Python的ORM介绍
  7. 如何用纯 CSS 创作一个小球反弹的动画
  8. 【mysql】【转发】Cannot proceed because system tables used by Event Scheduler were found damaged at server start
  9. Python3 S.join() 个人笔记
  10. apicloud入门学习笔记1:简单介绍