AtCoder AGC030C Coloring Torus (构造)

题目链接

https://atcoder.jp/contests/agc030/tasks/agc030_c

题解

没智商狗想起自己暑假时头铁60天刚这题最后无奈看题解的经历。。。
首先如果\(K\le 500\), 那么直接每行放一种颜色就行了。
但是其实还有一种办法是同一对角线放一种颜色。
那么现在，由于\(500\)是偶数，所以我们可以在同一对角线上交替地……放两种颜色。
然后……就完了。
时间复杂度与输出同阶。

题解

#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define riterator reverse_iterator
using namespace std;

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*10+ch-48;}
    return x*f;
}

const int N = 500;
int a[N+3][N+3];
int n;

int main()
{
    scanf("%d",&n);
    if(n<=N)
    {
        printf("%d\n",n);
        for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) printf("%d ",i); puts("");}
    }
    else
    {
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                if(i+N+1>n) {a[j][(i+j)%N] = i+1;}
                else {a[j][(i+j)%N] = j&1?i+1+N:i+1;}
            }
        }
        printf("%d\n",N);
        for(int i=0; i<N; i++) {for(int j=0; j<N; j++) printf("%d ",a[i][j]); puts("");}
    }
    return 0;
}