_no0B

Untitled

Nov 28th, 2021
592
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.  
  56.     /// problem: https://codeforces.com/problemset/problem/154/B
  57.     vector < int > prime = Sieve(1e5);
  58.  
  59.  
  60.     int n , m;
  61.     cin>>n>>m;
  62.  
  63.     for(int p:prime){
  64.         for(int multiple = p ; multiple <= n ; multiple += p){
  65.             primeSet[multiple].push_back(p);
  66.         }
  67.     } /// O( n*ln(n) )
  68.  
  69.     while(m--){
  70.         char opp;
  71.         int coll;
  72.         cin>>opp>>coll;
  73.         if(opp == '+'){
  74.             if(isOn[coll]) cout<<"Already on\n";
  75.             else{
  76.                 bool conflict = 0;
  77.                 for(int p:primeSet[coll]){
  78.                     if(primes[p] > 0){
  79.                         conflict = 1;
  80.                         cout<<"Conflicts with "<<primes[p]<<endl;
  81.                         break;
  82.                     }
  83.                 }
  84.                 if(conflict == 0){
  85.                     cout<<"Success\n";
  86.                     isOn[coll] = 1;
  87.                     for(int p:primeSet[coll]) primes[p] = coll;
  88.                 }
  89.             }
  90.         }
  91.         else{
  92.             if(isOn[coll] == 0) cout<<"Already off\n";
  93.             else{
  94.                 isOn[coll] = 0;
  95.                 cout<<"Success\n";
  96.                 for(int p:primeSet[coll]) primes[p] = 0;
  97.             }
  98.         }
  99.     }
  100.  
  101.     return 0;
  102.  
  103. }
  104.  
  105.  
RAW Paste Data