_no0B

Untitled

Nov 28th, 2021
572
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define N ((int)6e4 + 5)
  4. #define MOD ((int)1e9 + 7)
  5. #define MAX ((int)1e9 + 7)
  6. #define MAXL ((ll)1e18 + 7)
  7. #define MAXP ((int)1e3 + 7)
  8. #define thr 1e-8
  9. #define pi acos(-1)  /// pi = acos ( -1 )
  10. #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
  11. #define endl "\n"
  12.  
  13. using namespace std;
  14.  
  15. int isPrime[N/32 + 2];
  16.  
  17. bool IsPrime(int num) /// returns 1 for prime
  18. {
  19.     if(num == 2) return 1;
  20.     if((num & 1) == 0)  return 0;
  21.     int idx  = num >> 5 , bit = num & 31;
  22.     if( ( isPrime[idx] & (1<<bit) ) != 0 ) return 0;
  23.     else return 1;
  24. }
  25.  
  26. vector < int > Sieve(int n)
  27. {
  28.     for(int i = 3; i * i <= n ; i += 2){
  29.         if(IsPrime(i)){
  30.             for(int j = i * i ; j <= n ; j += i<<1){
  31.                 int idx = j >> 5 , bit = j & 31;
  32.                 isPrime[idx] = isPrime[idx] | (1<<bit);
  33.             }
  34.         }
  35.     }
  36.     vector < int > prime;
  37.     prime.push_back(2);
  38.     for(int i = 3 ; i <= n ; i += 2){
  39.         if(IsPrime(i)) prime.push_back(i);
  40.     }
  41.     return prime;
  42. }
  43.  
  44.  
  45.  
  46. vector < int > primeSet[N];
  47.  
  48. bool isOn[N];
  49.  
  50. int primes[N];
  51.  
  52.  
  53. int main()
  54. {
  55.     vector < int > prime = Sieve(1e5);
  56.  
  57.  
  58.     int n , m;
  59.     cin>>n>>m;
  60.  
  61.     for(int p:prime){
  62.         for(int multiple = p ; multiple <= n ; multiple += p){
  63.             primeSet[multiple].push_back(p);
  64.         }
  65.     } /// O( n*ln(n) )
  66.  
  67.     while(m--){
  68.         char opp;
  69.         int coll;
  70.         cin>>opp>>coll;
  71.         if(opp == '+'){
  72.             if(isOn[coll]) cout<<"Already on\n";
  73.             else{
  74.                 bool conflict = 0;
  75.                 for(int p:primeSet[coll]){
  76.                     if(primes[p] > 0){
  77.                         conflict = 1;
  78.                         cout<<"Conflicts with "<<primes[p]<<endl;
  79.                         break;
  80.                     }
  81.                 }
  82.                 if(conflict == 0){
  83.                     cout<<"Success\n";
  84.                     isOn[coll] = 1;
  85.                     for(int p:primeSet[coll]) primes[p] = coll;
  86.                 }
  87.             }
  88.         }
  89.         else{
  90.             if(isOn[coll] == 0) cout<<"Already off\n";
  91.             else{
  92.                 isOn[coll] = 0;
  93.                 cout<<"Success\n";
  94.                 for(int p:primeSet[coll]) primes[p] = 0;
  95.             }
  96.         }
  97.     }
  98.  
  99.     return 0;
  100.  
  101. }
  102.  
  103.  
RAW Paste Data