CSES - Putka Open 2015 – 2/6 - Results
Submission details
Task:Sudoku
Sender:
Submission time:2015-08-16 16:34:23 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED100
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.05 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.06 sdetails

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 1000000007
using 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);
else
ohi|=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
...