結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
|
提出日時 | 2020-11-30 21:57:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 2,960 bytes |
コンパイル時間 | 2,284 ms |
コンパイル使用メモリ | 199,848 KB |
最終ジャッジ日時 | 2025-01-16 10:32:32 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(ll i=0;i<n;i++)#define repl(i,l,r) for(ll i=(l);i<(r);i++)#define per(i,n) for(ll i=(n)-1;i>=0;i--)#define perl(i,r,l) for(ll i=r-1;i>=l;i--)#define fi first#define se second#define pb push_back#define ins insert#define pqueue(x) priority_queue<x,vector<x>,greater<x>>#define all(x) (x).begin(),(x).end()#define CST(x) cout<<fixed<<setprecision(x)#define vtpl(x,y,z) vector<tuple<x,y,z>>#define rev(x) reverse(x);using ll=long long;using vl=vector<ll>;using vvl=vector<vector<ll>>;using pl=pair<ll,ll>;using vpl=vector<pl>;using vvpl=vector<vpl>;const ll MOD=1000000007;const ll MOD9=998244353;const int inf=1e9+10;const ll INF=4e18;const ll dy[9]={0,0,1,-1,1,1,-1,-1,0};const ll dx[9]={1,-1,0,0,1,-1,1,-1,0};template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}const int MAX_ROW = 510; // to be set appropriatelyconst int MAX_COL = 510; // to be set appropriatelystruct BitMatrix {int H, W;bitset<MAX_COL> val[MAX_ROW];BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}inline bitset<MAX_COL>& operator [] (int i) {return val[i];}};int GaussJordan(BitMatrix &A, bool is_extended = false) {int rank = 0;for (int col = 0; col < A.W; ++col) {if (is_extended && col == A.W - 1) break;int pivot = -1;for (int row = rank; row < A.H; ++row) {if (A[row][col]) {pivot = row;break;}}if (pivot == -1) continue;swap(A[pivot], A[rank]);for (int row = 0; row < A.H; ++row) {if (row != rank && A[row][col]) A[row] ^= A[rank];}++rank;}return rank;}int linear_equation(BitMatrix A, vector<int> b, vector<int> &res) {int m = A.H, n = A.W;BitMatrix M(m, n + 1);for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) M[i][j] = A[i][j];M[i][n] = b[i];}int rank = GaussJordan(M, true);// check if it has no solutionfor (int row = rank; row < m; ++row) if (M[row][n]) return -1;// answerres.assign(n, 0);for (int i = 0; i < rank; ++i) res[i] = M[i][n];return rank;}int main(){ll n;cin >> n;vl v(n);rep(i,n)cin >> v[i];vector<int> b(n);rep(i,n)cin >> b[i],b[i]^=1;BitMatrix m(n,n);rep(i,n){ll l=(i+v[i])%n;ll r=(-v[i]+inf*n+i)%n;if(l==r){m[l][i]=1;}else{m[l][i]=1,m[r][i]=1;}}vector<int> ret;int ok=linear_equation(m,b,ret);//cout << ok <<endl;if(ok!=-1){cout << "Yes" <<endl;//rep(i,n)cout << ret[i] <<" ";cout << endl;}else cout << "No" <<endl;}