paulomiranda98

Código - 1671 - URI

Apr 18th, 2021
765
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define all(x) x.begin(),x.end()
  5. #define endl '\n'
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using pii = pair<int, int>;
  11. const int INF = 0x3f3f3f3f;
  12. const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  13. const int MOD = 1000000007;
  14. const int dx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
  15. const int dy[] = {-1, 1,  0, 0, 1, -1, -1,  1};
  16.  
  17. typedef pair<int, int> pii;
  18. template<bool directed=false> struct EulerianPath{
  19.   vector<vector<pii>> adj;
  20.   vector<int> ans, pos;
  21.   vector<bool> used;
  22.   int n, m;
  23.   EulerianPath(int n1){
  24.     n = n1; m = 0;
  25.     adj.assign(n, vector<pii>());
  26.   }
  27.   void addEdge(int a, int b) {
  28.     int at = m++;
  29.     adj[a].push_back({b, at});
  30.     if (!directed) adj[b].push_back({a, at});
  31.   }
  32.   void dfs(int u){
  33.     stack<int> st;
  34.     st.push(u);
  35.     while(!st.empty()){
  36.       u = st.top();
  37.       if(pos[u] < adj[u].size()){
  38.         auto [to, id] = adj[u][pos[u]];
  39.         pos[u]++;
  40.         if(!used[id]){
  41.           used[id] = true;
  42.           st.push(to);
  43.         }
  44.       }else{
  45.         ans.push_back(u);
  46.         st.pop();
  47.       }
  48.     }
  49.   }
  50.   // Remember to call the correct src
  51.   // If you want to check if there is an answer remember to check if all |components| > 1 of the graph are connected
  52.   vector<int> getPath(int src){
  53.     pos.assign(n, 0);
  54.     used.assign(m, false);
  55.     ans.clear();
  56.     dfs(src);
  57.     reverse(ans.begin(), ans.end());
  58.     return ans;
  59.   }
  60. };
  61. int main() {
  62.   ios_base::sync_with_stdio(false); cin.tie(NULL);
  63.   while(true){
  64.     int n;
  65.     cin >> n;
  66.     if(n == 0)
  67.       break;
  68.     if(n == 1){
  69.       cout << "0123456789" << endl;
  70.       continue;
  71.     }
  72.     int lim = 1;
  73.     for(int i=1; i<=n-1; i++)
  74.       lim *= 10;
  75.     EulerianPath<true> graph(lim);
  76.     for(int i=0; i<lim; i++){
  77.       for(int j=0; j<10; j++){
  78.         int next = (i*10 + j)%lim;
  79.         graph.addEdge(i, next);
  80.       }
  81.     }
  82.     string ans(n-2, '0');
  83.     auto path = graph.getPath(0);
  84.     for(int x: path){
  85.       ans += ('0' + (x%10));
  86.     }
  87.     cout << ans << endl;
  88.   }
  89.   return 0;
  90. }
  91.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×