QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#914916 | #1990. Restaurants | AA_Surely# | AC ✓ | 193ms | 68864kb | C++23 | 2.6kb | 2025-02-25 19:40:26 | 2025-02-25 19:40:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
#define fr first
#define sc second
#define vc vector
#define pb push_back
#define all(x) x.begin() , x.end()
#define Heh ios::sync_with_stdio(false) , cin.tie(0)
/*
const int MAXN = 1e3 + 13;
const ld err = 1e-12;
int par[MAXN] , rnk[MAXN];
int get(int v){return par[v] = (par[v] == v ? v : get(par[v]));}
void uni(int a , int b){
a = get(a) , b = get(b);
if(a == b) return;
if(rnk[a] < rnk[b]) swap(a , b);
par[b] = a;
rnk[a] += rnk[b];
}
ld dis(ld a , ld b , ld c , ld d){
return sqrt((a - c) * (a - c) + (b - d) * (b - d));
}
*/
ll pw(ll a , ll b , ll mod){
ll ret = 1;
while(b){
if(b&1) ret = (ret * a) % mod;
a = (a * a) % mod;
b /= 2;
}
return ret;
}
/*
const int MAXN = 3e5 + 35 , p = 313 , mod = 1e9 + 7;
string s;
int n , hsh[MAXN] , pp[MAXN] , inv[MAXN];
int hshsub(int l , int r){
int ret = hsh[r];
if(l){
ret -= hsh[l-1];
if(ret < 0) ret += mod;
}
ret = (1ll * ret * inv[l]) % mod;
return ret;
}
*/
int main(){
Heh;
int n , m;
cin >> n >> m;
int c[m];
for(int i = 0 ; i < m ; i++) cin >> c[i];
vc<int> pn[n];
cin.ignore();
for(int i = 0 ; i < n ; i++){
string s;
getline(cin , s);
s += ' ';
string t;
for(char c : s){
if(c == ' '){
if(t == "") continue;
pn[i].pb(stoi(t) - 1);
t = "";
}
else t += c;
}
}
vc<int> pm[m];
map<int,int> mpn[m];
for(int i = 0 ; i < m ; i++){
string s;
getline(cin , s);
s += ' ';
string t;
for(char c : s){
if(c == ' '){
if(t == "") continue;
pm[i].pb(stoi(t) - 1);
t = "";
}
else t += c;
}
for(int j = 0 ; j < (int)pm[i].size() ; j++){
mpn[i][pm[i][j]] = j;
}
}
int pt[n] = {};
set<int> atr[m];
queue<int> nos;
for(int i = 0 ; i < n ; i++) nos.push(i);
while(nos.size()){
int i = nos.front();
nos.pop();
while(pt[i] < pn[i].size()){
int j = pn[i][pt[i]];
if((int)atr[j].size() < c[j]){
atr[j].insert(mpn[j][i]);
break;
}
else if(*prev(atr[j].end()) > mpn[j][i]){
int k = pm[j][*prev(atr[j].end())];
atr[j].erase(prev(atr[j].end()));
nos.push(k);
atr[j].insert(mpn[j][i]);
break;
}
pt[i]++;
}
}
vc<int> ans;
for(int i = 0 ; i < m ; i++){
while(atr[i].size()){
ans.pb(pm[i][*atr[i].begin()]);
atr[i].erase(atr[i].begin());
}
}
sort(all(ans));
for(int x : ans) cout << x+1 << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3840kb
input:
5 2 2 1 1 2 1 2 1 5 3 1 2 4
output:
2 3 5
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
5 2 2 3 1 2 1 2 1 5 3 1 2 4
output:
2 3 4 5
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
5 6 1 5 5 5 5 5 1 1 1 1 1 3 1 5 4 2 0 0 0 0 0
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 3 1 1 1 1 2 2 3 1 3 2 3
output:
1 3
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 3 1 1 1 1 2 3 2 3 1 2 3 3 2
output:
1 2 3
result:
ok 3 lines
Test #6:
score: 0
Accepted
time: 107ms
memory: 59008kb
input:
1000 1000 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 50...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 1000 lines
Test #7:
score: 0
Accepted
time: 4ms
memory: 4864kb
input:
10000 1 5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 5053 5054 5055 5056 5057 5058 5059 5060 ...
result:
ok 5000 lines
Test #8:
score: 0
Accepted
time: 62ms
memory: 17848kb
input:
50000 4 5000 5000 5000 5000 2 1 3 4 3 2 4 1 4 3 2 1 2 4 3 1 1 3 2 4 3 1 4 2 3 4 2 1 2 1 3 4 2 3 4 1 2 1 4 3 2 4 3 1 2 4 1 3 1 2 4 3 1 2 4 3 4 1 3 2 2 4 1 3 1 4 3 2 1 4 2 3 3 4 1 2 4 3 1 2 1 4 3 2 3 4 1 2 4 2 1 3 2 4 1 3 2 3 1 4 3 1 2 4 1 2 4 3 4 2 3 1 1 2 3 4 1 2 4 3 1 2 3 4 4 3 1 2 4 1 3 2 3 1 4 2 ...
output:
30001 30002 30003 30004 30005 30006 30007 30008 30009 30010 30011 30012 30013 30014 30015 30016 30017 30018 30019 30020 30021 30022 30023 30024 30025 30026 30027 30028 30029 30030 30031 30032 30033 30034 30035 30036 30037 30038 30039 30040 30041 30042 30043 30044 30045 30046 30047 30048 30049 30050 ...
result:
ok 20000 lines
Test #9:
score: 0
Accepted
time: 5ms
memory: 7424kb
input:
10000 10000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 10000 lines
Test #10:
score: 0
Accepted
time: 63ms
memory: 22272kb
input:
10000 100 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50...
output:
1 2 4 5 9 17 18 20 24 25 27 28 31 32 33 34 35 36 37 38 40 44 45 46 47 49 51 53 55 56 59 61 63 64 65 66 67 69 71 73 76 81 83 86 87 88 90 92 93 94 96 99 101 105 107 108 112 114 115 116 118 121 126 127 130 131 133 135 136 137 141 144 145 146 150 156 157 159 160 161 163 164 165 169 172 179 181 184 185 1...
result:
ok 5000 lines
Test #11:
score: 0
Accepted
time: 155ms
memory: 67668kb
input:
50000 10000 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 50000 lines
Test #12:
score: 0
Accepted
time: 193ms
memory: 68864kb
input:
50000 10000 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 50000 lines
Test #13:
score: 0
Accepted
time: 178ms
memory: 64384kb
input:
50000 10000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 10000 lines