#1187930 (C++17(gcc12)) No.1971 Easy Sudoku

• 問題: No.1971 Easy Sudoku
• ユーザー: eiram
• 提出日時: 2026-09-19 10:16:31
• 言語: C++17(gcc12) (gcc 12.4.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 15,881 bytes
• コンパイル時間: 5,407 ms
• コンパイル使用メモリ: 293,308 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-19 10:16:46
• 合計ジャッジ時間: 6,546 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 13

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

#define INF 1LL<<60
#define MOD 998244353
#define MMOD 1000000007
using mint=modint998244353;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T> using vc=vector<T>;
template<typename T> using vv=vc<vc<T>>;
using vl=vector<ll>;
using vvl=vv<ll>;
using vs=vc<string>;
using vvs=vv<string>;
using vb=vc<bool>;
using vvb=vv<bool>;
using lP=pair<ll,ll>;
using vlp=vc<lP>;

template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}

#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define YN {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define all(a) a.begin(),a.end()
#define debug(var) cout << #var << " = " << var << endl;

template<class T> struct Edge {
    ll from;
    ll to;
    T val;
    Edge(ll f, ll t,T v) : from(f), to(t), val(v) { }
};
template<class T> using Graph=vector<vector<Edge<T>>>;

//下、上、右、左の順番
vl dx={0,0,1,-1,1,1,-1,-1};
vl dy={1,-1,0,0,1,-1,1,-1};

//最短経路を求め、復元できる。
template<class T> struct shortestpath {
    Graph<T> G;

    vl dist;
    vl prev;

    shortestpath() { }
    shortestpath(const Graph<T> &graph) { init(graph); }
    void init(const Graph<T> &graph) {
        G=graph;
        dist.assign(G.size(),INF);
        prev.assign(G.size(),-1);
    }

    void dijkstra(ll s){
        priority_queue<pair<ll,ll>,vector<lP>,greater<lP>> pq;
        dist[s]=0;
        pq.push({0,s});
        while(!pq.empty()){
            lP p=pq.top();
            ll d=p.first;
            ll v=p.second;
            pq.pop();
            if(d>dist[v]) continue;
            for(auto &e:G[v]){
                if(d+e.val<dist[e.to]){
                    dist[e.to]=d+e.val;
                    prev[e.to]=v;
                    pq.push({dist[e.to],e.to});
                }
            }
        }
    }

    vl restoration(ll g) {
        vl path;
        for(ll i=g;i!=-1;i=prev[i]){
            path.push_back(i);
        }
        reverse(all(path));
        return path;
    }

    //最短経路のパスを配列で返す。1→2→3みたいな。
    vl path(ll s,ll g){
        dijkstra(s);
        vl ans=restoration(g);
        return ans;
    }
};

template<class T> struct cycledetection {
    Graph<T> G;

    vb seen,finished;
    vc<Edge<T>> history;

    cycledetection() { }
    cycledetection(const Graph<T> &graph) { init(graph); }
    void init(const Graph<T> &graph) {
        G=graph;
        seen.assign(G.size(),false);
        finished.assign(G.size(),false);
    }

    ll dfs(ll v,const Edge<T> &e,bool is_prohibit_reverse=true){
        seen[v]=true;
        history.push_back(e);
        for(const Edge<T> &e2:G[v]){
            if(is_prohibit_reverse && e2.to==e.from) continue;
            if(finished[e2.to]) continue;
            if(seen[e2.to]&&!finished[e2.to]){
                history.push_back(e2);
                return e2.to;
            }
            ll pos=dfs(e2.to,e2,is_prohibit_reverse);
            if(pos!=-1) return pos;
        }
        finished[v]=true;
        history.pop_back();
        return -1;
    }

    vc<Edge<T>> reconstruct(ll pos) {
        vector<Edge<T>> cycle;
        while(!history.empty()){
            const Edge<T> &e=history.back();
            cycle.push_back(e);
            history.pop_back();
            if(e.from==pos) break;
        }
        reverse(all(cycle));
        return cycle;
    }

    vc<Edge<T>> detect(bool is_prohibit_reverse = true){
        ll pos=-1;
        for(ll v=0;v<(ll)G.size()&&pos==-1;++v){
            if(seen[v]) continue;
            history.clear();
            pos=dfs(v,Edge<T>(),is_prohibit_reverse);
            if(pos!=-1) return reconstruct(pos);
        }
        return vc<Edge<T>>();
    }
};

template<class T> vector<ll> dijkstra(Graph<T> &G,ll s){
    vl dist(ll(G.size()),INF);
    priority_queue<pair<ll,ll>,vector<lP>,greater<lP>> pq;
    dist[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        lP p=pq.top();
        ll d=p.first;
        ll v=p.second;
        pq.pop();
        if(d>dist[v]) continue;
        for(auto &e:G[v]){
            if(d+e.weight<dist[e.to]){
                dist[e.to]=d+e.weight;
                pq.push({dist[e.to],e.to});
            }
        }
    }
    return dist;
}

bool outgrid(ll y,ll x,ll h,ll w){
    return (y>=h||x>=w||y<0||x<0);
};

//Gにグラフ、sがスタート地点。sからの距離が返り値の配列に入る。グラフはvvl g(n)で良い。
vl bfs(vvl &G,ll s){
    vl dist(G.size(),INF);
    queue<ll> q;
    dist[s]=0;
    q.push(s);
    while(!q.empty()){
        ll v=q.front();
        q.pop();
        for(auto &e:G[v]){
            if(dist[e] != INF) continue;
            dist[e]=dist[v]+1;
            q.push(e);
        }
    }
    return dist;
};

//単純有向グラフの、頂点sを含む閉路の変数が最小の閉路の変数を求める。閉路が無かったら-1で返る。
ll cycleminedge(vvl &G/*,ll s*/){
    vl val=bfs(G,0);
    ll ans=INF;
    for(int v=0;v<(ll)G.size();v++){
        for(ll u:G[v]){
            if(u==0){
                ans=min(ans,val[v]+1);
            }
        }
    }
    if(ans==INF) return -1;
    return ans;
}

//壁がある時にcontinueするならコメントアウト外して！
vvl gridbfs(vs &G,ll sy,ll sx){
    vvl dist(G.size(),vl(G[0].size(),INF));
    queue<lP> q;
    dist[sy][sx]=0;
    q.push(make_pair(sy,sx));
    while(!q.empty()){
        lP p=q.front();
        ll y;
        ll x;
        tie(y,x)=p;
        q.pop();
        for(int i=0;i<4;i++){
            ll ny=y+dy[i];
            ll nx=x+dx[i];
            if(outgrid(ny,nx,G.size(),G[0].size())) continue;
            if(dist[ny][nx]!=INF) continue;
            // if(G[ny][nx]=='#') continue;
            dist[ny][nx]=dist[y][x]+1;
            q.push(make_pair(ny,nx));
        }
    }
    return dist;
}

vb vi;
//Gにグラフ、nowが今の場所。この分の上にvi書いてね。main内でviをresizeもしてね。
void dfs(vvl &G,ll now){
    vi[now]=true;
    for(auto &e:G[now]){
        if(vi[e]) continue;
        dfs(G,e);
    }
};

vb seen;
vb finished;
bool cycle=false;
//無向辺グラフのサイクルがあるか判定する。resizeしてね。結果はcycleにある。
void iscycledfs(vvl &G,ll now){
    seen[now]=true;
    for(auto &e:G[now]){
        if(seen[e]) continue;
        if(seen[e]&&!finished[e]){
            cycle=true;
        }
        dfs(G,e);
    }
    finished[now]=true;
};

ll pathcnt=0;
//n頂点全てを通るパスが何通りあるかをpathcntに記憶する。上にn宣言、main内でviをresizeしてね。cntは最初は1。コメントアウト外してね。
void pathdfs(vvl &G,ll now,ll cnt){
    vi[now]=true;
    //if(cnt==n) pathcnt++;
    for(auto &e:G[now]){
        if(vi[e]) continue;
        pathdfs(G,e,cnt+1);
    }
    vi[now]=false;
}

vv<bool> visi;
ll h,w;
//グリッド上DFS。探索して行けるとこはvisiがtrue,行けないとこはfalse。visiとh,wを上に！main内でvisiをresizeも！
void on_the_grid_dfs(vs &G,ll y,ll x){
    visi[y][x]=true;
    for(int i=0;i<4;i++){
        ll nx=x+dx[i];
        ll ny=y+dy[i];
        if(outgrid(ny,nx,h,w)) continue;
        if(visi[ny][nx]) continue;
        // if(G[ny][nx]=='#') continue;
        on_the_grid_dfs(G,ny,nx);
    }
};

struct unionfind{
    vl par,rank,siz; //par(x)=要素xの親頂点の番号（自身が根の場合は-1
                     //rank(x)=要素xの属する根付き木の高さ
                     //siz(x)=要素xの属する根付き木に含まれる頂点数
    unionfind(int n) :par(n,-1),rank(n,0),siz(n,1) { }

    ll root(ll x){
        if(par[x]==-1) return x;
        else return par[x]=root(par[x]);
    }
    bool issame(ll x,ll y){
        return root(x)==root(y);
    }
    void unite(ll x,ll y){
        x=root(x);
        y=root(y);
        if(x==y) return ;
        if(rank[x]<rank[y]){
            par[x]=y;
            siz[y]+=siz[x];
        }else{
            par[y]=x;
            siz[x]+=siz[y];
            if(rank[x]==rank[y]) ++rank[x];
        }
    }
    bool same(ll x,ll y){
        return root(x)==root(y);
    }
    ll size(ll x){
        return siz[root(x)];
    }

    //集合数（連結成分数）を返す。
    ll countsets(){
        ll cnt=0;
        for(ll i=0;i<ll(par.size()); ++i) if(root(i)==i)++cnt;
        return cnt;
    }
};

vector<pair<char,ll>> stringRLE(string s){
    vector<pair<char,ll>> rle;
    for(char c:s){
        if(rle.empty() || rle.back().first != c) rle.emplace_back(c,1);
        else rle.back().second++;
    }
    return rle;
};

//数値型の配列をランレングス圧縮する。引数の配列をsortしないと機能しないかもです。
vlp digitRLE(vl a){
    vlp rle;
    for(ll c:a){
        if(rle.empty() || rle.back().first != c) rle.emplace_back(c,1);
        else rle.back().second++;
    }
    return rle;
}

//2進数から10進数へ
ll base2to10(string s){
    ll n=s.size();
    ll ans=0;
    ll a=1;
    reverse(s.begin(),s.end());
    for(int i=0;i<n;i++){
        if(s[i]=='1') ans+=a;
        a*=2;
    }
    return ans;
};
//x進数から10進数へ
ll basexto10(string s,ll x){
    ll n=s.size();
    ll ans=0;
    ll a=1;
    reverse(s.begin(),s.end());
    for(int i=0;i<n;i++){
        if(s[i]!='0') ans+=a*(char(s[i]-'0'));
        a*=x;
    }
    return ans;
}

//10進数からx進数へ2<=x<=16(返り値は文字列型なので注意。)
string base10tox(ll n,ll x){
    string ans="";
    vc<char> digits={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    do{
        ans+=digits[n%x];
        n/=x;
    }while(n);
    reverse(ans.begin(),ans.end());
    return ans;
};

ld manhattan(ld x,ld y,ld x2,ld y2){
    return (abs(x-x2)+abs(y-y2));
};

ll gcd(ll a,ll b){
    while(a>=1&&b>=1){
        if(a<b) b=b%a;
        else a=a%b;
    }
    if(a>=1) return a;
    return b;
}

//nを素因数分解して、pairで(素数,指数)が返される。
vlp pfact(ll n){
    vlp a;
    for(ll i=2;i*i<=n;i++){
        if(n%i!=0) continue;
        ll ex=0;
        while(n%i==0){
            ex++;
            n/=i;
        }
        a.emplace_back(i,ex);
    }
    if(n!=1) a.emplace_back(n,1);
    return a;
}
//nを素因数分解して、配列で素数が返される。（総積がnになる）
vl pfact2(ll n){
    vl a;
    for(ll i=2;i*i<=n;i++){
        while(n%i==0){
            n/=i;
            a.push_back(i);
        }
    }
    if(n!=1) a.push_back(n);
    return a;
}

//n以下の整数について素数判定をしてnまでの素数が昇順に入ってる配列を返す。
vl eratosthenes(ll n){ 
    vb isprime(n,false);
    vl p;
    for(int i=2;i<n;i++){
        if(isprime[i]) continue;
        p.push_back(i);
        for(int j=i;j<n;j+=i) isprime[j]=true;
    }
    return p;
}

//時計回りに配列を回転させるa=rotate(a)って感じで使う。
vvl rotate(vvl a){
    vvl b(a.size(),vl(a[0].size()));
    for(ll i=1;i<=(ll)a.size();i++){
        for(ll j=1;j<=(ll)a[0].size();j++){
            b[i-1][j-1]=a[(a.size()+1-j)-1][i-1];
        }
    }
    return b;
}

//時計回りに文字列配列を回転させるa=rotate(a)って感じで使う。
vs string_rotate(vs a){
    vs b(a.size(),string(a.size(),'*'));
    for(ll i=1;i<=(ll)a.size();i++){
        for(ll j=1;j<=(ll)a[0].size();j++){
            b[i-1][j-1]=a[(a.size()+1-j)-1][i-1];
        }
    }
    return b;
}

//2つのグリッドで何箇所違う文字のところがあるか探索する。
ll differentcount(vs s,vs t){
    ll h=s.size(),w=s[0].size();
    ll cnt=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]!=t[i][j]) cnt++;
        }
    }
    return cnt;
}

//回文か判定する。回文ならtrue,じゃないならfalse
bool kaibun(string s){
    string t=s;
    reverse(t.begin(),t.end());
    if(t==s) return true;
    else return false;
}

//回文にするために何文字変えないといけないかを返す。
ll kaibuncnt(string s){
    ll ans=0;
    for(ll i=0;i<(ll)s.size()/2;i++){
        if(s[i]!=s[(s.size()-i)-1]) ans++;
    }
    return ans;
}

//1次元の累積和を返す。vl rui(n+1)=ruisekiwa1d(a)みたいに使う。
vl ruisekiwa1d(vl a){
    vl rui(a.size()+1,0);
    for(ll i=1;i<(ll)a.size()+1;i++){
        rui[i]=rui[i-1]+a[i-1];
    }
    return rui;
}

//nCrを返す。
ll comb(ll n ,ll r){
    if(n<r||r<0) return 0;
    if(r>n-r) r=n-r;
    ll res=1;
    for(ll i=1;i<=r;i++) res=res*(n-i+1)/i;
    return res;
}

//計算量はO(y)
ll powmod(ll x,ll y){
    ll res=1;
    for(ll i=0;i<y;i++){
        res=res*x%MMOD;
    }
    return res;
}

//nの約数を返す。
vl yakusu(ll n){
    vl ans;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            if(n/i==i){
                ans.push_back(i);
                continue;
            }
            ans.push_back(i);
            ans.push_back(n/i);
        }
    }
    return ans;
}

//グリッドの四隅を配列に入れる
vl yosumi(vs s){
    vl ans(4);
    ans[0]=1e9,ans[1]=0,ans[2]=1e9,ans[3]=0;
    for(ll i=0;i<(ll)s.size();i++){
        for(ll j=0;j<(ll)s[0].size();j++){
            if(s[i][j]=='#'){
                chmin(ans[0],i);
                chmax(ans[1],i);
                chmin(ans[2],j);
                chmax(ans[3],j);
            }
        }
    }
    return ans;
}

bool nibugurahu(vvl &G,ll s){
    vl iro(G.size(),-1);
    queue<ll> q;
    iro[s]=0;
    q.push(s);
    while(!q.empty()){
        ll v=q.front();
        q.pop();
        ll nuru=(iro[v] == 0 ? 1 : 0);
        for(auto &e:G[v]){
            if(iro[e] == -1) iro[e]=nuru,q.push(e);
            if(iro[v] == iro [e]) return false;  
        }
    }
    return true;
}

//a^b%mを求める
ll modpow(ll a,ll b,ll m){
    ll ans=1;
    while(b){
        if(b%2==1) ans=(ll)(ans)*a%m;
        a=(ll)(a)*a%m;
        b/=2;
    }
    return ans;
}

struct BIT{
    private:
        vl bit;
        ll n;
    
    public:
        BIT(ll size){
            n=size;
            bit.resize(n+1);
        }
    
    void add(ll a,ll w){
        for(ll x=a;x<n;x+=x&-x) bit[x]+=w;
    }

    ll sum(ll a){
        ll ret=0;
        a--;
        for(ll x=a;x>0;x-=x&-x) {
            ret+=bit[x];
        }
        return ret;
    }
};

string hidukeplus(string s) { //日付を一日進める。s=2025/4/25なら返り値は2025/4/26になる。
    ll y=stoll(s.substr(0,4));
    ll m=stoll(s.substr(5,2));
    ll d=stoll(s.substr(8,2));
    vl a={31,28,31,30,31,30,31,31,30,31,30,31};
    if(y%300==0||(y%100!=0&&y%4==0)) a[1]=29;
    if(a[m-1]==d) {
        d=1;
        if(m==12) {
            m=1;
            y++;
        }else m++;
    }else d++;
    string ans=to_string(y)+"/"+(to_string(m).size()==1? "0": "")+to_string(m)+"/"+(to_string(d).size()==1? "0": "")+to_string(d);
    return ans;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v){
    for (T &in : v) is>>in;
    return is;
}

template <typename T>
ostream &operator<<(ostream &os,const vector<T> &v) {
    for(ll i=0;i<(ll)v.size();i++){
        os<<v[i]<<(i + 1 !=(ll)v.size() ? " " : "");
    }
    return os;
}

//セグ木の二項演算　問題によって変える
ll op(ll a,ll b) { return max(a,b); }
//セグ木の初期値　問題によって変える
ll e() { return -1; }

struct Node {
    ll cnt = 0;
    map<char,Node*> to;
};

int main() {
    ll n;
    cin>>n;
    ll now=1;
    for(ll i=0;i<n;i++){
        now=i+1;
        for(ll j=0;j<n;j++){
            cout<<now<<" ";
            now%=n;
            now++;
        }
        cout<<endl;
    }
}