fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Song {
  5.   int num;
  6.   string artist;
  7.   vector<int> next_song;
  8.   int color;
  9.   Song(int nm, const string &a) : num(nm), artist(a), color(-1){};
  10. };
  11.  
  12. vector<Song*> songs;
  13.  
  14. // With 10 colors 9 artists are almost 4 times as likely to get unique colors
  15. // as with 9 colors. Prob of failing 2000 times is less than 1/1000
  16. const int TIMES = 2000;
  17. const int NCOLS = 10;
  18.  
  19. /* Assign random colors 0..NCOLS-1 to all songs. */
  20. void rnd_col(){
  21.   map<string, int> col;
  22.   for (vector<Song*>::const_iterator s = songs.begin(); s != songs.end(); ++s) {
  23.     if (col.count((*s)->artist) == 0) {
  24.       col[(*s)->artist] = rand() % NCOLS;
  25.     }
  26.     (*s)->color = col[(*s)->artist];
  27.   }
  28. }
  29.  
  30. /* last song in a playlist (prefix), pointing back to previous nodes */
  31. struct Node {
  32.   Song *last; // last song in playlist
  33.   int len;    // length of playlist
  34.   Node *prev; // previous node in playlist
  35.   int colors;    // colors used including last
  36.   Node(Song *lst, Node *p=0) : last(lst), len(1), prev(p), colors(1 << lst->color) {
  37.     if (prev) {
  38.       assert(!(colors & prev->colors));
  39.       len = 1 + prev->len;
  40.       colors |= prev->colors;
  41.     }
  42.   };
  43. };
  44.  
  45.  
  46. /* print solution (reversed following Node->prev */
  47. void print_sol(Node *n) {
  48.   if (n->prev) {
  49.     print_sol(n->prev);
  50.     cout << " ";
  51.   }
  52.   cout << n->last->num;
  53. }
  54.  
  55.  
  56. void solve() {
  57.   vector<int> seen(100*(1<<NCOLS), 0);
  58.   int gen=0;
  59.   bool success = false;
  60.   // try up to TIMES random NCOLS colorings then give up
  61.   for (int t = TIMES; t && !success; --t) {
  62.     ++gen;
  63.     // random coloring
  64.     rnd_col();
  65.  
  66.     // queue of nodes to expand, start with single songs
  67.     vector<Node*> q;
  68.     int head=0;
  69.  
  70.     for (int i=0; i < songs.size(); ++i) {
  71.       Node *n = new Node(songs[i]);
  72.       q.push_back(n);
  73.     }
  74.  
  75.     // BFS until empty queue or found length 9 playlist
  76.     while (head < q.size() && !success) {
  77.       // pop first node n and its song s
  78.       Node *n = q[head++];
  79.       Song *s = n->last;
  80.       // try all songs that can follow s
  81.       for (int i = 0; i < s->next_song.size(); ++i) {
  82.   Song *s1 = songs[s->next_song[i]];
  83.   // have we used color of s1 already?
  84.   int bit = (1 << s1->color);
  85.   if (n->colors & bit) continue;
  86.   // have we already pushed equivalent Node on stack?
  87.   int sig = (s1->num << NCOLS) + (n->colors | bit);
  88.   if (seen[sig] == gen) continue;
  89.   // add new node to queue
  90.   seen[sig] = gen;
  91.   Node *n1 = new Node(s1, n);
  92.   q.push_back(n1);
  93.   // if last node pushed completes playlist, success and print
  94.   if (n1->len == 9) {
  95.     success = true;
  96.     print_sol(n1);
  97.     cout << endl;
  98.     break;
  99.   }
  100.       }
  101.     }
  102.     // delete nodes allocated for this BFS
  103.     for (int i = 0; i < q.size(); ++i) delete q[i];
  104.   }
  105.   if (!success) cout << "fail" << endl;
  106. }
  107.  
  108. int main() {
  109.   srand(12345678);
  110.   string s;
  111.   int N;
  112.   int n;
  113.   int num=0;
  114.   for (cin >> N; N; --N) {
  115.     cin >> s >> n;
  116.     Song *song = new Song(++num, s);
  117.     int m;
  118.     for (int i=0; i < n; ++i) {
  119.       cin >> m;
  120.       song->next_song.push_back(m-1);
  121.     }
  122.     songs.push_back(song);
  123.   }
  124.   solve();
  125.   return 0;
  126. }
  127.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin 
10
asdd 2 10 3
fsb 1 6
dcsdg 2 1 5
dssdvs 1 9
sge 1 4
fsdg 1 2
gyk 2 6 8
hkfj 0
srsi 1 3
jjdyt 1 7
stdout 
5 4 9 3 1 10 7 6 2
https://ideone.com/qwDUVg
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!