fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <map>
  4. #include <string>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. int R, C, N;
  9. vector<string> names;
  10. vector<int> status; // 0 = GOODBOY, 1 = DISRUPTIVE
  11. map<string,int> id;
  12.  
  13. vector<pair<int,int>> friendships;
  14. vector<pair<int,int>> rivalries;
  15.  
  16. vector<vector<int>> adj; // adjacency list for grid
  17.  
  18. int bestAns = -1;
  19. vector<int> seat; // seat[pos] = student index
  20.  
  21. // cek validitas partial assignment
  22. bool validSoFar(int pos) {
  23.     int stu = seat[pos];
  24.     for (int nb : adj[pos]) {
  25.         if (nb >= pos) continue; // only check filled neighbors
  26.         int other = seat[nb];
  27.         if (other == -1) continue;
  28.         // Rule 1: rivals cannot be adjacent
  29.         for (auto &rv : rivalries) {
  30.             if ((rv.first == stu && rv.second == other) ||
  31.                 (rv.second == stu && rv.first == other))
  32.                 return false;
  33.         }
  34.         // Rule 2: both disruptive cannot be adjacent
  35.         if (status[stu] == 1 && status[other] == 1)
  36.             return false;
  37.     }
  38.     return true;
  39. }
  40.  
  41. void dfs(int pos, vector<int>& used) {
  42.     if (pos == R*C || (int)used.size() == N) {
  43.         // check friendship satisfaction
  44.         int cnt = 0;
  45.         for (auto &fr : friendships) {
  46.             int a = -1, b = -1;
  47.             for (int i = 0; i < R*C; i++) {
  48.                 if (seat[i] == fr.first) a = i;
  49.                 if (seat[i] == fr.second) b = i;
  50.             }
  51.             if (a != -1 && b != -1) {
  52.                 for (int nb : adj[a]) {
  53.                     if (nb == b) { cnt++; break; }
  54.                 }
  55.             }
  56.         }
  57.         bestAns = max(bestAns, cnt);
  58.         return;
  59.     }
  60.     if (pos >= R*C) return;
  61.  
  62.     // coba kosongkan kursi (kalau N < R*C)
  63.     seat[pos] = -1;
  64.     dfs(pos+1, used);
  65.     seat[pos] = -1;
  66.  
  67.     // coba tempatkan siswa yang belum dipakai
  68.     for (int s = 0; s < N; s++) {
  69.         if (find(used.begin(), used.end(), s) != used.end()) continue;
  70.         seat[pos] = s;
  71.         if (validSoFar(pos)) {
  72.             used.push_back(s);
  73.             dfs(pos+1, used);
  74.             used.pop_back();
  75.         }
  76.         seat[pos] = -1;
  77.     }
  78. }
  79.  
  80. int main() {
  81.     scanf("%d %d", &R, &C);
  82.     scanf("%d", &N);
  83.  
  84.     names.resize(N);
  85.     status.resize(N);
  86.     for (int i = 0; i < N; i++) {
  87.         char nm[20], st[20];
  88.         scanf("%s %s", nm, st);
  89.         names[i] = nm;
  90.         id[names[i]] = i;
  91.         status[i] = (st[0] == 'D'); // DISRUPTIVE -> 1
  92.     }
  93.  
  94.     int F; scanf("%d", &F);
  95.     friendships.resize(F);
  96.     for (int i = 0; i < F; i++) {
  97.         char a[20], b[20];
  98.         scanf("%s %s", a, b);
  99.         friendships[i] = {id[a], id[b]};
  100.     }
  101.  
  102.     int V; scanf("%d", &V);
  103.     rivalries.resize(V);
  104.     for (int i = 0; i < V; i++) {
  105.         char a[20], b[20];
  106.         scanf("%s %s", a, b);
  107.         rivalries[i] = {id[a], id[b]};
  108.     }
  109.  
  110.     // build adjacency
  111.     int total = R*C;
  112.     adj.assign(total, {});
  113.     for (int r = 0; r < R; r++) {
  114.         for (int c = 0; c < C; c++) {
  115.             int idx = r*C + c;
  116.             if (r > 0) adj[idx].push_back((r-1)*C + c);
  117.             if (r < R-1) adj[idx].push_back((r+1)*C + c);
  118.             if (c > 0) adj[idx].push_back(r*C + (c-1));
  119.             if (c < C-1) adj[idx].push_back(r*C + (c+1));
  120.         }
  121.     }
  122.  
  123.     seat.assign(total, -1);
  124.     vector<int> used;
  125.     dfs(0, used);
  126.  
  127.     if (bestAns == -1) printf("Impossible\n");
  128.     else printf("%d\n", bestAns);
  129.     return 0;
  130. }
  131.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Sh6Z8X
problem CFONISMG, based on SPOJ submission 35051415 (CPP14), 2025-09-30 17:07:06
language:
C++14 (gcc 8.3)
created:
4 hours 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!