?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
90474877 |
Practice: dragon__knight |
1392E - 26 | C++17 (GCC 7-32) | Wrong answer on test 3 | 15 ms | 8 KB | 2020-08-20 18:12:02 | 2020-08-20 18:12:02 |
#include <bits/stdc++.h> #define ll long long #define mod (ll)(1e9+7) using namespace std; int n; vector<pair<int,int>> ans; bool find_path( const vector<vector<ll>>& v, ll s, int x, int y, ll cur ) { if(x == n-1 && y == n-1) { if(cur+v[x][y] == s) { ans.push_back(make_pair(x+1,y+1)); return true; } else { return false; } } if(x < n-1 && find_path(v, s, x+1, y, cur+v[x][y])) { ans.push_back(make_pair(x+1, y+1)); return true; } if(y < n-1 && find_path(v, s, x, y+1, cur+v[x][y])) { ans.push_back(make_pair(x+1, y+1)); return true; } return false; } int main(void) { cin>>n; vector<vector<ll>> v(n,vector<ll>(n)); vector<vector<ll>> s(n,vector<ll>(n)); ll sum = 1; v[0][0] = s[0][0] = 0; //st.insert(0); for(int i=1; i<n; i++) { v[0][i] = sum-s[0][i-1]; s[0][i] = sum; ++sum; } for(int i=1; i<n; i++) { v[i][0] = sum-s[i-1][0]; s[i][0] = sum; ++sum; } for(int i=1; i<n; i++) { for(int j=1; j<n; j++) { v[i][j] = sum - min(s[i-1][j], s[i][j-1]); sum = v[i][j] + max(s[i-1][j], s[i][j-1])+1; } } for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { cout << v[i][j] << " " ; cout.flush(); } cout << endl; cout.flush(); } int q; cin>>q; while(q--) { cin>>sum; ans.clear(); find_path(v,sum,0,0,0); for(int i=ans.size()-1; i>=0; i--) { cout << ans[i].first << " " << ans[i].second << endl; cout.flush(); } } return 0; }
?
?
?
?