Task: | Sudoku |
Sender: | |
Submission time: | 2015-08-16 16:34:23 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 100 |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.05 s | details |
#3 | ACCEPTED | 0.05 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.06 s | details |
Code
#include <bits/stdc++.h>#define ll long long#define ull unsigned long long#define pii pair<int, int>#define pll pair<long long, long long>#define defmod 1000000007using namespace std;int su[9][9] = {0};int n = 9;void dbg(){for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cout << su[i][j];}cout << endl;}}bool onkook(){for(int i = 0; i < 9; i++){bool kay[10] = {0};for(int j = 0; j < 9; j++)kay[su[i][j]] = 1;for(int j = 1; j <= 9; j++)if(!kay[j])return false;}for(int i = 0; i < 9; i++){bool kay[10] = {0};for(int j = 0; j < 9; j++)kay[su[j][i]] = 1;for(int j = 1; j <= 9; j++)if(!kay[j])return false;}vector<pair<int, int> > v;v.push_back({0, 0});v.push_back({3, 0});v.push_back({6, 0});v.push_back({0, 3});v.push_back({3, 3});v.push_back({6, 3});v.push_back({0, 6});v.push_back({3, 6});v.push_back({6, 6});for(auto f: v){int i = f.first;int j = f.second;bool kay[10] = {0};for(int k = i/3*3; k < (i+3)/3*3; k++){for(int l = j/3*3; l < (j+3)/3*3; l++){kay[su[k][l]] = 1;//d[k][l] = 1;//cout << "kaydaan " << k << ", " << l << endl;}}for(int j = 1; j <= 9; j++)if(!kay[j])return false;}return true;}bool hae(int r, int t){//cout << "nyt " << r << " " << t << endl;if(r >= 9){bool lol = onkook();//dbg();//cout << lol << " oliko oikein" << endl;//int tmp; cin >> tmp;return lol;}deque<int> jee;int i = r; int j = t;//cout << "paikka " << i << ", " << j << ":" << endl;vector<bool> kay(10, 1);//bool d[9][9] = {0};for(int k = j-1; k >= 0; k--){kay[su[i][k]] = 0;//d[i][k] = 1;//cout << "kaydaan " << i << ", " << k << endl;}for(int k = i-1; k >= 0; k--){kay[su[k][j]] = 0;//d[k][j] = 1;//cout << "kaydaan " << k << ", " << j << endl;}for(int k = i/3*3; k < (i+3)/3*3; k++){for(int l = j/3*3; l < (j+3)/3*3; l++){kay[su[k][l]] = 0;//d[k][l] = 1;//cout << "kaydaan " << k << ", " << l << endl;}}/*cout << endl;for(int o = 0; o < n; o++){for(int p = 0; p < n; p++){cout << d[o][p];}cout << endl;}*/for(int k = 1; k <= 9; k++){if(kay[k]){jee.push_back(k);}}bool ohi = false;while(!jee.empty()){su[r][t] = jee.front();jee.pop_front();if(t >= 8)ohi|=hae(r+1, 0);elseohi|=hae(r, t+1);if(ohi)return true;}su[r][t] = 0;return ohi;}int main(){cin.sync_with_stdio(0);cin.tie(0);string s; cin >> s;for(int i = 0; i < n; i++){su[0][i] = s[i]-'0';}hae(1, 0);for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cout << su[i][j];}cout << endl;}return 0;}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
592836471 |
correct output |
---|
592836471 836471592 471592836 928364715 364715928 ... |
user output |
---|
592836471 134257689 678149235 213465798 456798123 ... |
Test 2
Verdict: ACCEPTED
input |
---|
672935418 |
correct output |
---|
672935418 935418672 418672935 729354186 354186729 ... |
user output |
---|
672935418 134268579 589147236 213456897 456789123 ... |
Test 3
Verdict: ACCEPTED
input |
---|
329174658 |
correct output |
---|
329174658 174658329 658329174 291746583 746583291 ... |
user output |
---|
329174658 145268379 678359124 213485796 456791283 ... |
Test 4
Verdict: ACCEPTED
input |
---|
376958421 |
correct output |
---|
376958421 958421376 421376958 769584213 584213769 ... |
user output |
---|
376958421 124367589 589124367 213475698 457689132 ... |
Test 5
Verdict: ACCEPTED
input |
---|
875694321 |
correct output |
---|
875694321 694321875 321875694 756943218 943218756 ... |
user output |
---|
875694321 123578469 469123578 214356897 356789142 ... |