QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87703#2302. KnitpickingBitrollAC ✓3ms3572kbC++171.7kb2023-03-14 02:33:592023-03-14 02:34:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 02:34:03]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3572kb
  • [2023-03-14 02:33:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

// debug util
#ifdef DEBUG
    #define deb(x) cerr << #x << " = " << x << endl
#else
    #define deb(x)
#endif

// useful
#define ll long long
#define umap unordered_map
bool multi = false;

void solve(){
    int n, k, tsocks = 0; cin >> n;
    string type, fit; 

    // [left, right, any]
    map<string, array<int, 3>> socks; 

    // Receive each group
    while(n--){
        cin >> type >> fit >> k;
        
        // Socks types counter
        if(socks.find(type) == socks.end()) tsocks++; 

        if(fit == "any"){
            socks[type][2] = k;
        }else if(fit == "left"){
            socks[type][0] = k;
        }else {
            socks[type][1] = k;
        }
    }

    // Iterate each key and find the worst case
    map<string, array<int, 3>>::iterator it = socks.begin();
    int global_worst = 0; 
    int impossible_count = 0; 
    
    while(it != socks.end()){
        int left, right, any;
        string key = it -> first;
        left = it->second[0];
        right = it->second[1];
        any = it->second[2];

        int limited_any = min(1, any);
        int lr_max = max(left, right);
        int local_worst = max(limited_any, lr_max); // Local worst case
        global_worst += local_worst;  // Increment the global worst
        
        if((any <= 1) && (left == 0 || right == 0)) impossible_count++; 
		it++; 
	}
	
	
	impossible_count == tsocks ? cout << "impossible" : cout << global_worst + 1; 
	cout << endl; 
	
	// deb(tsocks); 
	// deb(global_worst); 
	// cout << global_worst << endl; 
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    if(multi)cin>>t;
    while(t--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3420kb

input:

1
a right 1

output:

impossible

result:

ok single line: 'impossible'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3492kb

input:

1000
ehtxfswvjctflpymwvpu left 490
aoarodkjmvfxjzmuywws right 441
wbiwtrdrmtonomjlacny left 593
lxargqrkcbibrpgvbmtn left 451
xegwrtwznrhpziuduohf left 999
hfrbhoyemnooutcraxea right 323
etrytrwvzohcieikbuzj right 737
upzpwtidbyyyixrgcubf left 165
triwxccjjyggvyhetzjg left 956
emoedagctbncppybklmz l...

output:

484655

result:

ok single line: '484655'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3520kb

input:

1000
fdfjrkigimhdklwpbjfq any 1
orplbnusrtnywcabovuz any 1
fcwqvjhmgxpqrgbnltuu right 456
qokzqcteopapcayzvojp right 601
xyawkinqjmntqlkeuaqp left 334
gwjngblhxjimeylrfchk right 839
etxefreizcivrcppreww any 1
xxkhaiwbafmujafffvdj right 924
japbjgqtamzwzavzvopw right 33
fvvdtprtiwjindtweztm any 1
gyg...

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0
Accepted
time: 3ms
memory: 3572kb

input:

1000
sdmahapqooqcoblpaxmo left 745
vbnuuavqxbmrirmzjdwb right 555
wfnnnzoahqnechdacthx left 666
vshsbtdxehcnzfzfczeb any 1
dlhelxzpyswaidvxsgkz any 1
xzebrtcoidsxmacqdwwk right 831
skyalmvvwtbahyjmjgfr left 80
oizpvmqqohpkbtbfjtzs any 1
mouekxvcnodieywzzjyf left 7
kinkwztsuaedroqtqfvq right 226
imkp...

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

1
abcdefghijklmnopqrst left 1

output:

impossible

result:

ok single line: 'impossible'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3436kb

input:

1
uiop any 1

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3416kb

input:

1
jgekwa any 2

output:

2

result:

ok single line: '2'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3368kb

input:

2
abc any 1
def any 1

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3380kb

input:

2
abcdefghijklmnopqrst left 1
abcdefghijklmnopqrs right 1

output:

impossible

result:

ok single line: 'impossible'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3496kb

input:

1000
dtgjmpfmfrzqbkwglebv right 570
kamutdycrgqvcsmwirmx right 299
dwbpezcdfalnciietkvd left 247
aqsjcvqdyyxlzruixsfa any 71
vpmamejtjqrrevvkngep left 767
hptokkxkgoztyltvzrxm left 860
uadkjbvbluvqdksokrsu left 706
orwrzcnsivmjiilnbunk any 947
fwyvlvkkuqllhaatrwex any 592
pquobafvipupxbnbxqix left 8...

output:

322825

result:

ok single line: '322825'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3512kb

input:

1000
ztsperflliyvjtbbfyai left 701
badhiuvrlitwhepbyjlf right 949
fbtzlwohuarinunogvsu left 97
rnepyxvexwndagobprbw right 845
jwhldxdblplcqdxsaauw left 501
feusgzbqyjmqqcxaipdh right 591
jotvmufuzgzhvfpnumzf left 859
jtngpfpgewevswqfcjhy left 337
iscnejfxdtiomzbomxif any 874
nahzsgamkgmlhnstcvbj any...

output:

335450

result:

ok single line: '335450'

Test #12:

score: 0
Accepted
time: 3ms
memory: 3508kb

input:

1000
tydqoybipmdvxdqoqwab left 466
tynaskmzsiiaqlykjuop right 454
sqfxvbievqdygnivbrhx right 778
qvzvdynxtmhxzeiqlttw right 181
oguecwewwvedomokglyj right 739
cidzezvrvoahrrtfsplx left 7
jjvmfpjfotdolwvqrbyn left 208
vnsmpdomgdjtrwvpgpvy left 581
ceigkyfkagkmbnklzobv left 771
woaxtaukuekkhpnmbksv le...

output:

493798

result:

ok single line: '493798'